kmp基础

佚名 6年前 (2019-04-08) 随笔 670人围观抢沙发百度已收录

int nex[100000+5];
int lenp,lens;
int p[10000+5];//可以是char 也可以是string
int s[1000000+5];
void getnext()
{
    nex[0]=-1;
    int k=-1,j=0;
    while(j<lenp-1)
    {
        if(k==-1||p[j]==p[k])
            nex[++j]=++k;
        else k=nex[k];
    }
}
int kmp()
{   
    //lens=
    //lenp=
    int j=0;
    int i=0;
    while(i<lens&&j<lenp)
    {
        if(s[i]==p[j]||j==-1)
        {
            i++;
            j++;
        }
        else
            j=nex[j];

        if(j==lenp)
        {
            return i-j+1;
        }
    }
    return -1;
}