[ create a new paste ] login | about

Link: http://codepad.org/grtqfF5f    [ raw code | output | fork ]

C, pasted on Jul 22:
#include <stdio.h>
#include <string.h>
/* KMP algorithm for string Matching */
main()
{
  char *p="This is my first post to this group";
  char *T="to this group this is my post";
  int len = strlen(p);
  int len1 = strlen(T);
  printf("len:%d len1:%d\n",len,len1);
  int k = 0,i;
  int array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  /* Pre processing which takes O(m)*/
  for(i = 2; i< len; i++)
  {
     while(k > 0 && p[k+1] != p[i])
     {
        k = array[k];
     }
         
     if(p[k+1] == p[i])
     {
        k++;
        array[i] = k;
     }
  }
  
  /* Matching which takes O(n) */
  k = 1;
  for(i = 0; i< len1; i++)
  {
     
     while(k > 0 && p[k+1] != T[i])
     {   
        k = array[k];
     }
     
     if(p[k+1] == T[i])
     {
       k++;
       printf("%d %d %c\n",k,i,p[k]);
       if(k == 10)
       {
         printf("String Matched\n");
       }
     }
  }
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
len:35 len1:29
1 4 h
2 5 i
3 6 s
4 7  
1 15 h
2 16 i
3 17 s
4 18  
5 19 i
6 20 s
7 21  
8 22 m
9 23 y
10 24  
String Matched

Exited: ExitFailure 104


Create a new paste based on this one


Comments: