Question

跪求大神写一段代码，采用KMP算法，在主串中求模式串的next函数值！主串：abcabcd 模式串bcd！跪求.....

Answer 1

• 求next程序代码：

void  getNext(char*p,int*next) 

{     

    int   j,k;     

    next[0]=-1; j=0;k=-1;   

    while(j<strlen(p)-1)

    {         

        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]         

        {           

             j++;             

             k++;             

             next[j]=k;         

        }         

        else          //p[j]!=p[k]             

            k=next[k];     

    } 

}   

• KMP算法主程序：

int   KMPMatch(char*s, char*p)

{     

    int    next[100];     

    int    i,j;  i=0;  j=0;     

    getNext( p, next );   

    while( i < strlen(s) ){         

        if(j==-1||s[i]==p[j])         

        {           

            i++;             

            j++;         

        }

        else

        {             

            j=next[j];       //消除了指针i的回溯         

        }         

        if(j==strlen(p))           

            return    i-strlen(p);     

    }     

    return-1; 

}