//////////////////////////////////////////////////        /*KMP算法*/         #include<stdio.h>        #include<string.h>        #include<iostream>        using namespace std;                void getNext(char a[],int next[]){            int i,j;            next[1] = 0;            j = 0;            i = 2;            int m = strlen(a)-1; //从a[1]开始             while(i<=m){                if(a[j+1] == a[i]){                    j++; next[i++] = j;                }                else if(j==0){                    next[i++] = 0;                }else if(j>0){                    j = next[j];                }             }        }        int match(char a[],char b[],int next[]){            int i=0,j=0;            int pos;            int n = strlen(a)-1;            int m = strlen(b)-1;            while(1){                if(i>n) {                    pos = -1; break;                }                if(j==m){                    //pos = i-j+1; break;                    cout<<i-j+1<<"  "<<endl; j=next[j];                }                if(b[j+1] == a[i+1] ){                    j++; i++;                }else{                    if(j==0) i++;                    else if (j>0){                        j = next[j];                    }                }            }           }         /*        int main()       {              //char b[] = "!ababbc";            char b[] = "!abab";            int l = strlen(b);           int *next = new int[l-1];           getNext(b,next);           int i;           for(i=1;i<=l-1;i++){               printf("%d ",next[i]);           }           cout<<endl;           char a[] = "!ababababbc";           int pos = match(a,b,next);           cout<<endl<<pos<<endl;       }       */        //////////////////////////////////////////////////////        /*       KMP应用： 求一个串中所有前缀等于后缀的子串长度        */        void output(int i,int next[]){            while(next[i]>0){                cout<<next[i]<<" ";                i = next[i];            }        }        /*       int main()       {              char b[] = "!ababa";            int l = strlen(b);           int *next = new int[l-1];           getNext(b,next);           int i;           for(i=1;i<=l-1;i++){               printf("%d ",next[i]);           }           cout<<endl;           output(l-1,next);           delete[] next;       }       */