字符串KMP算法详解

引入

字符串kmp算法用于解决字符串匹配的问题：

给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l, r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。 现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。

• 很显然，我们能够想到暴力求解：

cin>>s1>>s2;
ll lena=s1.size(),lenb=s2.size();
for(int i=0;i<=lena-lenb;++i){
  bool flag=0;
  for(int j=i,k=1;j<i+lenb;++j,++k){
      if(s1[j]!=s2[k]){
           flag=1;
           break;
      }
  }
  if(!flag)cout<<i+1<<'\n';
}

时间复杂度为 \(O(nm)\) ，显然是不被接受的。

• 接下来我们可以想到 字符串哈希

  字符串哈希详解

#include<iostream>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int N=1e6+10;
ull h[N],hs=0;
char s[N],t[N];
ull qp(ull x,ull y)
{
  ull now=x,ans=1;
  while(y)
  {
      if(y&1)
          ans*=now;
      now*=now;
      y>>=1;
  }
  return ans;
}
int main()
{
  cin>>s+1>>t+1;
  int l1=strlen(s+1),l2=strlen(t+1);
  for(int i=1;i<=l1;++i)
      h[i] = h[i-1]*131ull+s[i];
  for(int i=1;i<=l2;++i)
      hs = hs*131ull+t[i];
  int ans=0;
  for(int i=l2;i<=l1;++i)
  {
      ull now=h[i]-h[i-l2]*qp(131,l2);
      if(now==hs)
          ans++;
  } 
  cout<<ans<<endl;
  return 0;
}

我们假设所给定的字符串允许 \(k\) 次失配 ， 时间复杂度为：\(O(m+kn· log_2^{m})\)

即使算法加入二分优化也卡不过硬性的匹配数据。

—— 那么，我们就可以考虑 字符串kmp算法

字符串kmp

设 \(s1 = a b a c a b a b , s2 = ababc\)

一开始，我们从 \(i=0\) 开始匹配：

kmp算法的具体思路是当我们发现某一个字符串不匹配的时候，由于已经知道之前遍历过的字符，利用这些信息来做一个 backup 的操作。

用上面的例子，我们在主串中搜索 \(ababc\) 发现最后一个字符不匹配。由于我们知道上面读过那些字符，我们将字串移动到这个位置：

接着进行匹配，由于这里的 \(AB\) 和主串的 \(AB\) 相同，我们完全可以跳过他们，直接进行下一步的匹配：

那我们怎么知道要跳过多少个字符呢？

——那就要用到 kmp 算法中的 next 数组了。

kmp算法在匹配失败的时候：

我们回去看最后一个匹配字符的next值：

例如此处是 \(2\) 然后直接跳过 \(2\) 个字符：

这里 \(2\) 代表子串中我们可以跳过的字符，也就是说前面的这个 \(AB\) 不需要看了，直接进行下一步匹配：

很显然，这样操作是没有问题的，因为主串中跳过的这两个 \(AB\) 确实可以和子串中的 \(AB\) 匹配上。所以我们只需要继续匹配后面的字符即可。

由于不用把时间浪费在无意义的失配上，效率自然也提高了不少。