KMP算法

对于串s[1..n]，我们定义fail[i]表示以串s[1..i]的最长公共真前后缀。

我们首先考虑对于模式串p，如何计算出它的fail数组。定义fail[0]=-1。

根据“真前后缀”的条件，容易得到fail[1]=0
对于任意的i>1，显然在s[fail[i-1]+1]==s[i]的时候，我们有fail[i]=fail[i-1]
如果s[fail[i-1]+1]!=s[i]，那么我们需要去尝试s[fail[fail[i-1]]+1]是否与s[i]相等，否则再继续下去。

这是因为我们最终要找的是s[1..i]的最长公共前后缀，如果它不是由s[1..i-1]的最长公共前后缀扩增而来，那么它一定是由s[1..fail[i-1]]的最长公共前后缀扩增而来。毕竟，最长公共前后缀包含了若干个公共前后缀。即s[1..fail[i-1]]的最长公共前后缀也是s[1..i-1]的一个公共前后缀，虽然它未必最长。

// Build fail array for pattern string

    for(int i=;i<=m;i++) {

        fail[i]=fail[i-];

        while(p[fail[i]+]-p[i] && fail[i]) fail[i]=fail[fail[i]];

        if(p[fail[i]+]==p[i]) ++fail[i];

    }
　　fail[0]=-1;

预处理完毕后，匹配过程与其大同小异。

我们需要定义两个指针i,j，指向当前希望要匹配的两个字符。

如果s[i]!=p[j]，则需要将模式串向右滑移，即j=fail[j-1]+1。当然如果j=0了，则重设j=1，并将模式串起点向右移动一位。

如果s[i]==p[j]，当模式串没有匹配完全即j<m时，将两个指针同时向右移动即可。如果匹配完了，则报告一个结果，并将模式串按j=fail[j-1]+1进行滑移，以便于进行下一次匹配。

for(int i=,j=;i<=n;) {

        if(s[i]==p[j]) {

            if(j<m) ++i,++j;

            else {

                cout<<i-m+<<endl;

                j=fail[j-]+;

            }

        }

        else {

            j=fail[j-]+;

            if(j<=) j=,i++;

        }

    }

算法总体复杂度O(n+m)。

完整模板：

#include <bits/stdc++.h>

using namespace std;

char s[],p[];

int n,m,fail[];

int main() {

    ios::sync_with_stdio(false);

    cin>>s+>>p+;

    n=strlen(s+); m=strlen(p+);

    // Build fail array for pattern string

    for(int i=;i<=m;i++) {

        fail[i]=fail[i-];

        while(p[fail[i]+]-p[i] && fail[i]) fail[i]=fail[fail[i]];

        if(p[fail[i]+]==p[i]) ++fail[i];

    }

    fail[]=-;

    for(int i=,j=;i<=n;) {

        if(s[i]==p[j]) {

            if(j<m) ++i,++j;

            else {

                cout<<i-m+<<endl;

                j=fail[j-]+;

            }

        }

        else {

            j=fail[j-]+;

            if(j<=) j=,i++;

        }

    }

    for(int i=;i<=m;i++) cout<<(fail[i]<?:fail[i])<<" ";

    cout<<endl;

}

#10046. 「一本通 2.2 练习 2」OKR-Periods of Words

容易发现这里我们要的其实是每个前缀减去最短的Border。类似并查集一样路径压缩一下即可。需要注意一些细节防止死循环。

#include <bits/stdc++.h>

using namespace std;

char s[], p[];

int n, m, fail[];

int main() {

    ios::sync_with_stdio(false);

    cin >> m;

    cin >> p + ;

    // Build fail array for pattern string

    long long ans = ;

    fail[] = ;

    for (int i = ; i <= m; i++) {

        fail[i] = fail[i - ];

        while (p[fail[i] + ] - p[i] && fail[i]) fail[i] = fail[fail[i]];

        if (p[fail[i] + ] == p[i])

            ++fail[i];

    }

    fail[] = -;

    for (int i = ; i <= m; i++) {

        int j = i;

        while (fail[j] > ) j = fail[j];

        ans += i - j;

        if (fail[i])

            fail[i] = j;

    }

    cout << ans << endl;

}

#10047. 「一本通 2.2 练习 3」似乎在梦中见过的样子

#include <bits/stdc++.h>

using namespace std;

char s[],p[];

int n,m,k,fail[],f[];

long long ans = ;

int main() {

    ios::sync_with_stdio(false);

    cin>>p+>>k;

    m=strlen(p+);

    while(m) {

        for(int i=;i<=m;i++) {

            fail[i]=fail[i-];

            while(p[fail[i]+]-p[i] && fail[i]) fail[i]=fail[fail[i]];

            if(p[fail[i]+]==p[i]) ++fail[i];

            if(f[fail[i]]) f[i]=f[fail[i]];

            else if(fail[i]>=k) f[i]=fail[i];

            else f[i]=;

            if(f[i] && (f[i]*)<i) ++ans;

        }

        --m;

        for(int i=;i<=m;i++) p[i]=p[i+];

        memset(fail,,sizeof fail);

        memset(f,,sizeof f);

    }

    cout<<ans<<endl;

}

#10048. 「一本通 2.2 练习 4」Censoring

搞个栈记录输出，顺便存下每个被输出点匹配到模式串的哪个位置

这样如果匹配就弹掉栈顶几个，并读取新栈顶原先匹配到了哪个位置，接下去匹配即可

#include <bits/stdc++.h>

using namespace std;

char s[],p[];

int n,m,fail[],sta[],staj[],top;

int main() {

    ios::sync_with_stdio(false);

    cin>>s+>>p+;

    n=strlen(s+); m=strlen(p+);

    for(int i=;i<=m;i++) {

        fail[i]=fail[i-];

        while(p[fail[i]+]-p[i] && fail[i]) fail[i]=fail[fail[i]];

        if(p[fail[i]+]==p[i]) ++fail[i];

    }

    fail[]=-;

    for(int i=,j=;i<=n;) {

        if(s[i]==p[j]) {

            if(j<m) ++top,sta[top]=i,staj[top]=j,++i,++j;

            else top-=m-,j=staj[top]+,++i;

        }

        else {

            j=fail[j-]+;

            if(j<=) ++top,sta[top]=i,staj[top]=j,i++;

        }

    }

    for(int i=;i<=top;i++) cout<<s[sta[i]];

    cout<<endl;

}

#include <bits/stdc++.h>using namespace std;
char s[100005],p[100005];int n,m,k,fail[100005],f[100005];long long ans = 0;
int main() {ios::sync_with_stdio(false);cin>>p+1>>k;m=strlen(p+1);while(m) { for(int i=2;i<=m;i++) { fail[i]=fail[i-1]; while(p[fail[i]+1]-p[i] && fail[i]) fail[i]=fail[fail[i]]; if(p[fail[i]+1]==p[i]) ++fail[i]; if(f[fail[i]]) f[i]=f[fail[i]]; else if(fail[i]>=k) f[i]=fail[i]; else f[i]=0; if(f[i] && (f[i]*2)<i) ++ans; } --m; for(int i=1;i<=m;i++) p[i]=p[i+1]; memset(fail,0,sizeof fail); memset(f,0,sizeof f);}cout<<ans<<endl;}

巴特西

[一本通学习笔记] KMP算法

#10046. 「一本通 2.2 练习 2」OKR-Periods of Words

#10047. 「一本通 2.2 练习 3」似乎在梦中见过的样子

#10048. 「一本通 2.2 练习 4」Censoring

最新文章

热门文章