首页 > 代码库 > KMP模板

KMP模板

void getnext() 
{
    next[0]=-1;
    for(int i=1;i<n;i++)
    {
        int j=next[i-1];
        while(t[j+1]!=t[i]&&j>-1)
            j=next[j];
        next[i]=(t[j+1]==t[i])?j+1:-1;
    }
}

int kmp()
{
    int i=j=0;
    while(i<slen&&j<plen)
    {
        if(j==-1||s[i]==p[j])
            i++,j++;
        else
            j=next[j];  
    }
    return (j==plen)?i-j:-1;
}

  

KMP模板