codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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"); } } } }
Private
[
?
]
Run code
Submit