Kmp--P3375 【模板】KMP字符串匹配

把已经给出的串称为文本串，要在文本串中找的串称为模式串。特别地，前两位$（kmp[0],kmp[1]）$为零。比如串$ABABAC$，它的$fail$应该为001230。
已知第$i$位的自动机$kmp[i]$，要求第$i+1$位的。设$j=kmp[i]$。$kmp[i]$一定在i前面，$kmp[i]$已经求好了。如果字符串的$i$和$j+1$位不同$（s2[i]≠s2[j+1]）$，那么j不断地跳到自己的自动机$kmp[j]$，直到匹配上或$j=0$为止。如果匹配上，$f[i] = j+1$；否则如果还是$s2[i]≠s2[j+1]$，说明是$j=0$而不是匹配上了，那么$kmp[j] = 0$。

构建自动机：

  j=;

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

        while(j&&b[i]!=b[j+])

        //此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳了

        j=kmp[j];

         //通过自己匹配自己来得出每一个点的kmp值

        if(b[j+]==b[i])j++;

        kmp[i]=j;

         //i+1失配后应该如何跳

        }

我们已经对该子串构建了一个自动机，当两个字符串相比较，如果失配，即$s1[i]!=s2[j+1]$就跳回，此时一定两位匹配$（j！=0）$或从头开始$（j=0）$，之后再匹配下一位即可。

运行自动机：

   int j;

     j=;//j可以看做表示当前已经匹配完的模式串的最后一位的位置

     //也可以理解为j表示模式串匹配到第几位了

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

           while(j&&b[j+]!=a[i])j=kmp[j];

           //如果失配 ，那么就不断向回跳，直到可以继续匹配

           if (b[j+]==a[i]) j++;

           //如果匹配成功，那么对应的模式串位置++

           if (j==lb) {

           cout<<i-lb+<<endl;

           j=kmp[j];

           //继续匹配

           }

        }

完整代码：

 #include<iostream>

 #include<cstring>

 #define MAXN 1000010

 using namespace std;

 int kmp[MAXN];

 int la,lb,j;

 char a[MAXN],b[MAXN];

 int main()

 {

     cin>>a+;

     cin>>b+;

     la=strlen(a+);

     lb=strlen(b+);

     for (int i=;i<=lb;i++)

        {

        while(j&&b[i]!=b[j+])

         j=kmp[j];

        if(b[j+]==b[i])j++;

         kmp[i]=j;

        }

     j=;

     for(int i=;i<=la;i++)

        {

           while(j>&&b[j+]!=a[i])

            j=kmp[j];

           if (b[j+]==a[i])

            j++;

           if (j==lb) {cout<<i-lb+<<endl;j=kmp[j];}

        }

     for (int i=;i<=lb;i++)

     cout<<kmp[i]<<" ";

     return ;

 }

巴特西

Kmp--P3375 【模板】KMP字符串匹配

最新文章

热门文章