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

以下面的字符串为例：

比较 ↓
主串 A B B A B B A B A B A A A B A B A A A
字串 A B B A B A A B A B A A

KMP 算法做了这样一件事：

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

比较 ↓
主串 A B B A B B A B A B A A A B A B A A A
字串 A B B A B A A B A B A A

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

上面是比较形象化的描述，当我们仔细看模式串时，会发现，在和主串对比前，可以对模式串进行预处理。以 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 为例，给出题解如下：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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;
}