//////////////////////////////////////////////////  
    /*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; 
    } 
    */