123456789101112131415161718192021222324252627 |
- void kmp_pre(char x[], int m, int pnext[]) {
- int i,j;
- j=pnext[0]=-1;
- i=0;
- while (i<m) {
- while (-1!=j && x[i]!=x[j]) j=pnext[j];
- pnext[++i]=++j;
- }
- }
- // x pattern, y text
- // answer: first index (starting with 0)
- // KMP_Count : # occurences
- int pnext[100005];
- int KMP(char x[], int m, char y[], int n) { // KMP_Count
- int i,j; // int ans = 0;
- kmp_pre(x,m,pnext);
- i=j=0;
- while(i<n) {
- while(-1!=j && y[i]!=x[j]) j=pnext[j];
- i++; j++;
- if (j>=m) {
- return i-m; // ans++; j=pnext[j];
- }
- }
- return -1; // return ans;
- }
|