KMP 算法

皮康龙发布

KMP 算法是一种快速将模式串与主串匹配的算法。

以下面的字符串为例:

比较
主串ABBABBABABAAABABAAA
子串ABBABAABABAA

KMP 算法做了这样一件事:

先比较第一个字母,A==A,「比较指针」后移一位,然后比较第二个字母,也相等……一直到 ABBAB==ABBAB。当比较第 6 个字母时,发现 B 不等于 A。于是,在这个时候选择研究之前匹配成功的 ABBAB。我们要找这个匹配成功的子串的最长的相等的前缀和后缀,在这个例子中是 AB,即 (AB)B(AB)。于是,我们将整个模式串后移,将之前的前缀移动到后缀的位置,接着和主串比较。即:

比较
主串ABBABBABABAAABABAAA
子串ABBABAABABAA

接下来接着比较主串和子串,当出现不同时还是找最长相同前后缀,当比较指针到子串末尾,或子串在移动后超出了主串末尾时,比较结束,返回成功或失败。

上面是比较形象化的描述,当我们仔细看模式串时,会发现,在和主串对比前,可以对模式串进行预处理。以 ABABAAABABAA 为例,

  • 当第 1 个字母 A 与主串不匹配时,将 1 号位与主串下一位比较。
  • 当第 2 个字母 B 与主串不匹配时,最长相同前后缀长度为 0,1 号位与主串当前位比较。
  • 当第 3 个字母 A 与主串不匹配时,最长相同前后缀长度为 0,1 号位与主串当前位比较。
  • 当第 4 个字母 B 与主串不匹配时,最长相同前后缀长度为 1,2 号位与主串当前位比较。
  • 当第 5 个字母 A 与主串不匹配时,最长相同前后缀长度为 2,3 号位与主串当前位比较。
  • 当第 6 个字母 A 与主串不匹配时,最长相同前后缀长度为 3,4 号位与主串当前位比较。
  • 当第 7 个字母 A 与主串不匹配时,最长相同前后缀长度为 1,2 号位与主串当前位比较。
  • ……

我们发现,除第一个字母外,当其他的字母与主串不匹配时,如果最长相同前后缀长度为 ,则 x + 1​ 号位与主串当前位比较。

我们将第一个字母对应的指令取 0,其他的取最长后缀长度 +1,得到 next 数组:[0, 1, 1, 2, 3, 4, 2, ...]

这样在比较的时候调用 next 数组即可。

值得注意的是,查阅资料后发现大部分 next 数组都是从 1 下标开始保存的,0 下标一般存储数组长度。

以 CF535D 为例,给出题解如下:

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
char p[N];
int x[N], _next[N];
long long qmi(long long a, long long b, long long m){
    a %= m;
    long long res = 1;
    while(b > 0){
        if(b & 1){
        	res = res * a % m;
		}
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main(){
	int n, m, cnt=0;
	scanf("%d%d%s", &n, &m, p+1);
	for(int i = 1; i <= m; i++){
		scanf("%d", x+i);
	}
	_next[0] = strlen(p+1);
	for(int i = 2; i <= _next[0]; i++){
		int j = _next[i-1];
		while(p[j+1] != p[i] && j){
			j = _next[j];
		}
		if(p[j+1] == p[i]){
			j++;
		}
		_next[i] = j;
	}
	sort(x+1, x+m+1);
	for(int i = 1; i <= m; i++){
		if(i==1 || x[i]-x[i-1]>=_next[0]){
			cnt += _next[0];
		}else{
			bool flag = false;
			int j = _next[_next[0]], l = x[i-1]+_next[0]-x[i];
			while(j){
				if(j==l){
					flag = true;
					cnt += _next[0]-l;
					break;
				}
				j = _next[j];
			}
			if(!flag){
				puts("0");
				return 0;
			}
		}
	}
    printf("%lld\n", qmi(26, n - cnt, 1000000007));
	return 0;
}
分类: 未分类

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注