KMP字符串匹配

发表于

KMP算法可在一个主文本串 S 内查找一个词 W 的出现位置
此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

朴素

有一个文本串S，和一个模式串P (两者长度分别为N,M)

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

时间复杂度 O(N*M)

KMP

核心思想就是通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

方法

  1. 对模式串B自我匹配，求出next数组，其中next[i]表示A中以i结尾的后缀串与前缀串的最大匹配长度

  2. 对A和B进行匹配，求出数组f，其中f[i]表示A中以i结尾的字串与B的前缀能匹配的最大长度

经过优化 在O(N+M)的复杂度内便可求解

next数组

首先 举个例子
设B=’abababa’,next[7]=?
b[2~7]=’bababa’ b[1~6]=’ababab’ 不匹配
b[3~7]=’ababa’ b[1~5]=’ababa’ 长度为5
…………
最后得next[7]=5
那么，我们如何求next数组呢？

选择相应的例子进行比较，我们显然能发现next数组中的递推关系

  1. 初始化next[1]=0
  2. 假设next[1~i-i]已求出 求next[i] 拓展长度j
  3. 如果拓展失败，即下个字符不相等，则令j变为next[j],直至j=0(应从头匹配)
  4. 如果拓展成功 匹配长度j+1
  5. 最后next[i]就为j

f数组

根据定义的相似性，求解f与求解next数组类似，此处不再细说

移动位数 = 已匹配的字符数 - 对应的部分匹配值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <cstdio>
#include <cstring>
using namespace std;
char a[66666666],b[66666666];
int next[66666666],f[66666666],n,m;
void KMP(){
 next[1]=0;
 for(int i=2,j=0;i<=m;++i){
  while(j>0&&b[i]!=b[j+1])j=next[j];
  if(b[i]==b[j+1])j++;
  next[i]=j;
 }
 for(int i=1,j=0;i<=n;++i){
  while(j>0&&(j==n||a[i]!=b[j+1]))j=next[j];
  if(a[i]==b[j+1])j++;
  f[i]=j;
 }
}
int main(){
 scanf("%s%s",a+1,b+1);
 n=strlen(a+1),m=strlen(b+1);
 KMP();
 /***********
 THIS IS A TEST
	
 printf("%s\n",a+1);
 for(int i=1;i<=n;++i)printf("%d",f[i]);
 printf("\n");
 printf("%s\n",b+1);
 for(int i=1;i<=m;++i)printf("%d",next[i]);
 ************/
}

附：然而，kmp并不是效率最高的算法，实际应用并不多，真正常见的是Boyer-Moore算法 相关资料
阮一峰的博客