字符串专题之KMP算法

写点自己对KMP的理解，我们有两个字符串A和B，求A中B出现了多少次。

这种问题就可以用KMP来求解。

朴素的匹配最坏情况是O(n^2)的。KMP是个高效的算法，效率是O(n)的。

KMP算法的思想是先将B串与自己匹配，预处理出一个kmp(next)数组，在失配的时候回跳，这样就大大提升了效率。

定义上kmp[1]为-1。暂时就先这样用吧。

 #pragma GCC optimize(2)

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 char a[maxn],b[maxn];

 int kmp[maxn];

 int main()

 {

     scanf("%s%s",a+,b+);

     int alen=strlen(a+);

     int blen=strlen(b+);

     for(int i=,j=;i<=blen;++i)

     {

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

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

         kmp[i]=j;

     }

     int ans=;

     for(int i=,j=;i<=alen;++i)

     {

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

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

         if(j==blen)ans++;

     }

     kmp[]=-;

     for(int i=;i<=blen;++i)printf("%d ",kmp[i]);

     printf("\n%d\n",ans);

     return ;

 }

给几道例题

洛谷P3375

hdu1686

hdu1711

hdu2087