拓展kmp

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//s从0到n-1
vi _kmp(const char *s,int n){
    vi t(n);
    t[0]=n;
    for (int i=1,p=-1,k=0;i<n;i++)
    {
        if (p>=i) t[i]=min(p-i+1,t[i-k]);
        while (i+t[i]<n && s[i+t[i]]==s[t[i]]) t[i]++;
        if (p<i+t[i]-1) p=i+t[i]-1,k=i;
    }
    return t;
}
}}}

//s从0到n-1
vi _kmp(const char *s,int n){
    vi t(n);
    t[0]=n;
    for (int i=1,p=-1,k=0;i<n;i++)
    {
        if (p>=i) t[i]=min(p-i+1,t[i-k]);
        while (i+t[i]<n && s[i+t[i]]==s[t[i]]) t[i]++;
        if (p<i+t[i]-1) p=i+t[i]-1,k=i;
    }
    return t;
}