KMP算法
KMP算法
前述：
以下讨论字符串下标均从0开始
解决的问题：
一个文本串$S$(主串)和一个模式串$P$，求$P$在$S$中出现的位置，或者$P$在$S$中出现的次数，等等问题。
暴力做法：
复杂度是$O(n*m)$,$n$是$P$的长度,$m$是$S$的长度
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e3+100;
char s[MAX_N], p[MAX_N];
// 返回P在S中的出现次数
int solve(char P[], int n, char S[], int m){
int ans = 0;
int i,j;
for(i = 0; i+n <= m; ++i){
for(j = 0; j < n; ++j){
if(S[i+j] != P[j]){
break;
}
}
if(j == n) {
ans++;
}
}
return ans;
}
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> s >> p;
dbg(solve(p, strlen(p), s, strlen(s)))
return 0;
}讨论：
暴力做法，字符失配以后，模式串往后移动一步，重新开始匹配
S: ABCDABCDABDE
P: ABCDABD
此时在$i=6$且$j=6$处失配($i$表示指向$S$的下标，$j$表示指向$P$的下标)，由于失配，按照暴力做法，下一步的比较是下面这样的：
S: ABCDABCDABDE
P: ABCDABD
此时$i=1$，$j=0$重新开始比较
KMP的做法：发生不匹配的时候，$i$不移动，直接移动模式串的位置，也就是$j$的位置，假设新的$j$的位置是$k(k < j)$，那么要求尽可能大的$k$使得：
$S[i-k…i-1]=P[0…k-1]$（式子1）
失配的前提条件是：
$S[i-j…i-1] = P[0…j-1]$，并且$S[i] != P[j]$（式子2），
由于$k < j$，由式子2可得：
$S[i-k…i-1] = P[j-k…j-1]$（式子3）
那么由式子1和式子3可得$P[0…k-1]=P[j-k…j-1]$
下面用文字的方式来解释：
式子2表示$P$的长度是$j$的前缀等于$S$的长度是$i$的前缀的长度是$j$的后缀，然后此时$S[i] != P[j]$，也就是失配了，我们知道了前面相等的匹配信息，所以不能浪费这些信息。
式子1表示我们不动下标$i$，只动下标$j$，然后使得$P$的长度是$k$的前缀等于$S$的长度是$i$的前缀的长度是$k$的后缀。然后$k < j$并且$k$越大越好。
由式子2我们推出式子3，也就是$P$的长度是$j$的前缀的长度是$k$的后缀等于$S$的长度是$i$的前缀的长度是$k$的后缀。
根据上面的叙述，我们定义一个数组$next$：
$next[j] = k$，表示到$S[i] != P[j]$的时候，下一步$j$指针需要跳到$k$的位置
由上面的分析可以知道。$next[j]=k$表示为满足$P[0…k-1] = P[j-k…j-1]$的最大$k$
文字解释：
$next[j]$表示字符串$P$的长度是$j$的前缀的前缀和后缀相等的最大长度
P：ABCDABD
next：-1 0 0 0 0 1 2 0
如何求解next数组：
求解$next$数组的代码
void kmp_pre(char P[], int m, int nxt[]){
int i = 0, j = nxt[0] = -1;
while(i < m){
while(j != -1 && P[i] != P[j]) j = nxt[j];
nxt[++i] = ++j;
}
}当前我们已经知道$next[i] = j$，那么可知$P[0…j-1]=P[i-j…i-1]$，如果$P[i] == P[j]$，那么就是$P[0…j]=P[i-j…i]$，那么可以推知$next[i+1]=next[j+1]$，等价于$next[++i]=next[++j]$，如果$P[i] != P[j]$那么令$j=next[j]$，我们已经知道$P[0…next[j]-1]=P[i-next[j]…i-1]$，同样的道理，这样继续下去。可以看出$next$数组是字符串$P$自己和自己匹配的结果。
next数组的其他操作：
1.next数组的跳转：
沿着next数组一直往前，得到的是所有即使前缀也是后缀的字符串
next数组往前跳的步数的步长是一样的，除了最后一次
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
P | A | B | C | A | B | C | A | B | C | A | B | |
next | -1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
从11开始跳：
得到11，8，5，2，0
从10开始跳：
得到10，7，4，1，0
从9开始跳：
得到9，6，3，0
从8开始跳：
得到8，5，2，0
等等。。。可以看出步长都是3
从11开始跳到8得到字符串AB
从8跳到5得到字符串ABCAB
从5跳到2得到字符串ABCABCAB
从2跳到0得到字符串ABCABCABCAB
以上四个字符串就是字符串$P$的既是前缀也是后缀的字符串
2.周期性字符串
如果$n \mod (n-next[n]) == 0$，那么循环节的长度是$n-next[n]$
推导一下： 对于模式串$P$有它的前缀$P[0…next[n]-1]$有$P[0…next[n]-1]=P[n-next[n]…n-1]$，通俗的说就是对于串$P[0…n-1]$，它的前半段长度是$k$的串和它的后半段长度是$k$的串相等。那么$n-next[n]$长的字符串就是后面的$P[n-(n-next[n])…n-1]$，也就是$P[next[n]…n-1]$，假设现在条件成立，即$n \mod (n-next[n]) == 0$，对于$next[next[n]]$，有$P[0…next[next[n]]-1]=P[next[n]-next[next[n]]…next[n]-1]$
综上可以推出:$P[next[next[n]]…next[n]-1] = P[next[n]…n-1]$
同样的道理推下去就可以知道循环节的长度是$n-next[n]$
举个例子：
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
P | a | b | c | a | b | c | a | b | c | a | b | c | |
next | -1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
条件：
条件1：
(abcabcabc) abc
abc (abcabcabc)
$P[0…next[n]-1]=P[n-next[n]…n-1]$
条件2：
(abcabc) abcabc
abc (abcabc) abc
$P[0…next[next[n]]-1]=P[next[n]-next[next[n]]…next[n]-1]$
推出结论：
(abcabc) [abc] abc
abc (abcabc) [abc]
$P[next[next[n]]…next[n]-1] = P[next[n]…n-1]$
相关题目练习：
1.POJ3461
题目描述：
给$t$组数据，每一组数据给两个字符串$W$和$T$，求字符串$W$在字符串$T$的出现次数
题解：
直接上kmp就完事了
#include <string>
#include <iostream>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
int t;
string W, T;
int m,n;
const int MAX_M = 1e4+100;
int nxt[MAX_M];
void solve(){
m = W.size();
int i,j;
j = nxt[0] = -1;
i = 0;
while(i < m){
while(j != -1 && W[i] != W[j]) j = nxt[j];
nxt[++i] = ++j;
}
int ans = 0;
n = T.size();
for(i = 0, j = 0; i < n; ++i){
if(j < m && W[j] == T[i]){
++j;
} else {
while(j > 0){
j = nxt[j];
if(W[j] == T[i]){
++j;
break;
}
}
}
if(j == m) ++ans;
}
cout << ans << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> t;
while(t--){
cin >> W >> T;
solve();
}
return 0;
}2.hdu1711
题目描述：
有两个序列一个是长度为$n$的数字序列$a$，一个是长度是$m$的数字序列$b$，求最小的$k$使得$a[k…k+m-1] = b[1…m]$
题解：
就是求$b$在$a$中第一次出现的位置，直接上kmp就完事了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e6+100;
const int MAX_M = 1e4+100;
int a[MAX_N], b[MAX_M];
int nxt[MAX_M];
int n,m;
int T;
void solve(){
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < m; ++i) cin >> b[i];
int i = 0, j = nxt[0] = -1;
while(i < m){
while(j != -1 && b[i] != b[j]) j = nxt[j];
nxt[++i] = ++j;
}
for(i = 0, j = 0; i < n; ++i){
if(j < m && a[i] == b[j]){
++j;
} else {
while(j > 0){
j = nxt[j];
if(a[i] == b[j]){
++j;
break;
}
}
}
if(j == m) {
cout << i-m+2 << endl;
return;
}
}
cout << "-1" << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) solve();
return 0;
}
/*
a[k...k+m-1] = b[1...m]
*/3.poj1961
题目描述：
求一个字符串的前缀中的周期性字符串个数
题解：
利用$next$数组的性质求解
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e6+100;
int nxt[MAX_N];
int n;
string s;
void solve(int t){
cin >> s;
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
cout << "Test case #" << t << endl;
for(int i = 2; i <= n; ++i){
if(i%(i-nxt[i]) == 0){
int k = i/(i-nxt[i]);
if(k > 1) cout << i << " " << k << endl;
}
}
cout << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
int t = 0;
while(cin >> n && n) {
solve(++t);
}
return 0;
}4.poj2406
题目描述：
求一个字符串由几个周期性字符串构成
题解：
解法大致同上一题
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e6+100;
char s[MAX_N];
int nxt[MAX_N];
int main(){
//freopen("in.txt", "r", stdin);
while(~scanf("%s", s) && s[0] != '.'){
int i = 0, j = nxt[0] = -1;
int n = strlen(s);
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
printf("%d\n", n%(n-nxt[n]) ? 1 : n/(n-nxt[n]));
}
return 0;
}5.hdu3336
题目描述：
求一个字符串中前缀在该字符串中出现的次数总和
题解：
解法1：
$dp[i]$ 表示长度是$i$的前缀的出现次数
$nxt[i]$表示前缀是$i$的字符串的前缀和后缀相等的最大长度
也就是说只要是长度为$i$的前缀在字符串中出现
容易知道$dp[i]$的初始值均为1
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 2e5+100;
const int MOD = 10007;
int T;
int n;
char s[MAX_N];
int nxt[MAX_N];
int dp[MAX_N];
void solve(){
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int ans = 0;
for(int i = 1; i <= n; ++i) dp[i] = 1;
for(int i = n; i >= 1; --i){
dp[nxt[i]] = dp[nxt[i]] + dp[i];
ans = (ans + dp[i]) % MOD;
}
cout << ans << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) {
cin >> n;
cin >> s;
solve();
}
return 0;
}解法2：
$dp[i]$表示前$i$个字符中前缀的匹配次数，显然$dp[0]=0$
动态转移方程$dp[i]=dp[nxt[i]]+1$
也就是说：前$i$个字符中前缀的匹配次数等于前$nxt[i]$中前缀的匹配次数加上1，
加上的1显然就是长度为$i$的前缀
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 2e5+100;
const int MOD = 10007;
int T;
int n;
char s[MAX_N];
int nxt[MAX_N];
int dp[MAX_N];
void solve(){
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int ans = 0;
dp[0] = 0;
for(int i = 1; i <= n; ++i){
dp[i] = dp[nxt[i]] + 1;
ans = (ans + dp[i]) % MOD;
}
cout << ans << endl;
}
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) {
cin >> n;
cin >> s;
solve();
}
return 0;
}6.hdu3746
题目描述：
求最少在一个字符串后面条件多少个字符使得该字符串是一个周期性字符串
题解：
由next数组的周期性可以知道。令$rem = n - next[n]$，可以知道当前字符串被分成若干段长度是$rem$的字符串，但是最后一段长度不一定是$rem$，所以只要看模数是多少，补齐使得对$rem$取余是0就行了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e5+100;
int T;
char s[MAX_N];
int nxt[MAX_N];
void solve(){
int i = 0, j = nxt[0] = -1;
int n = strlen(s);
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int rem = n-nxt[n];
int mod = n%rem;
if(nxt[n] == 0) cout << n << endl;
else cout << (rem-mod) % rem << endl;
}
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) {
cin >> s;
solve();
}
return 0;
}7.hdu2594
题目描述：
求$s1$的前缀和$s2$的后缀的最大匹配
题解：
下面的做法是错误的，但是交上去还是对了，数据弱得一皮，过不了下面这一组数据
xxoooxxxxxxxxx ooo
将$s1$和$s2$拼接成为$s$，求$s$的$nxt$数组。如果$nxt[n]==0$那么答案就是0这个显而易见。如果$nxt[n] <= min(|s1|, |s2|)$，那么答案长度就是$nxt[n]$，(错误分析开始)如果$nxt[n] > min(|s1|,|s2|)$，那么长度取$min(|s1|, |s2|)$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e5+100;
string s1, s2;
int nxt[MAX_N];
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
while(cin >> s1 >> s2){
int x = s1.size();
int y = s2.size();
string s = s1+s2;
int n = s.size();
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
if(nxt[n]) {
int len = min(min(x, y), nxt[n]);
cout << s.substr(0, len) << " " << len << endl;
} else cout << "0" << endl;
}
return 0;
}正确做法:
将$s1$和$s2$连接成$s$，求$s$的$next$数组，从$n$开始跳，直到跳到某个$j$使得$next[j] <= mn(|s1|, |s2|)$。这个其实用到了$next$数组的那个周期性的性质。每次跳的步数是$n-next[n]$，也就是说每次不要的字符串长度是$n-next[n]$这么长，最后得到的字符串长度$<=min(|s1|, |s2|)$而且相等。kmp的$next$数组简直就是米奇妙妙屋
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e5+100;
string s1, s2;
int nxt[MAX_N];
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
while(cin >> s1 >> s2){
int x = s1.size();
int y = s2.size();
int mn = min(x, y);
string s = s1+s2;
int n = s.size();
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int len = nxt[n];
j = n;
while(len > mn){ // nxt[j] <= mn
j = nxt[j];
len = nxt[j];
}
if(len) cout << s.substr(0, len) << " " << len << endl;
else cout << "0" << endl;
}
return 0;
}
/*
(xxooo)xxxxxxx(xxooo)
*/8.poj2185
题目描述：
给一个字符串矩阵，求一个最小的矩阵使得把这个矩阵循环重复铺开之后它的一个子矩阵是给的那个矩阵
题解：
按行看，把每一行当一个字母，得到一个字符串，求这个字符串的$next$数组，则答案矩阵的$r = R - nxt[R]$，同样道理按列看，求得$c = C - nxt[C]$，答案为$r * c$。
#include <iostream>
#include <string>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_R = 1e4+100;
const int MAX_C = 100;
int nxt[MAX_R];
int R,C;
string s[MAX_R];
string t[MAX_C];
int main(){
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> R >> C;
for(int i = 0; i < R; ++i){
cin >> s[i];
}
int i = 0, j = nxt[0] = -1;
while(i < R){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int r = R - nxt[R];
for(int j = 0; j < C; ++j){
t[j] = "";
for(int i = 0; i < R; ++i){
t[j] += s[i][j];
}
}
i = 0, j = nxt[0] = -1;
while(i < C){
while(j != -1 && t[i] != t[j]) j = nxt[j];
nxt[++i] = ++j;
}
int c = C - nxt[C];
cout << r * c << endl;
return 0;
}9.hdu4763
题目描述：
在一个字符串$s$中求一个子串$t$，使得$t$在$s$的前，中，后位置都有匹配。
题解：
根据$next$数组的含义，$next[i]$表示字符串$s$的长度是$i$的前缀中的相等的最长前缀和后缀。所以答案就是$min(next[n], max(next[1…n-1]))$。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e6+100;
char s[MAX_N];
int nxt[MAX_N];
int T;
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--){
cin >> s;
int n = strlen(s);
int i = 0, j = nxt[0] = -1;
while(i < n){
while(j != -1 && s[i] != s[j]) j = nxt[j];
nxt[++i] = ++j;
}
int mx = nxt[1];
for(int i = 2; i <= n-1; ++i) mx = max(mx, nxt[i]);
cout << min(mx, nxt[n]) << endl;
}
return 0;
}10.hdu6153
题目描述：
有两个字符串$s1$和$s2$，令$s2$的某一个后缀的权值是长度乘上该后缀在$s1$中的出现次数，求$s2$的所有后缀的权值和对$1e9+7$取模的值
题解：
首先想办法求$s2$中某一个后缀在$s1$中的出现次数。将$s1$和$s2$都逆序，问题就转换横求$s2$中的某一个前缀在$s1$中出现的次数。和hdu3336类似，hdu3336求的是
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e6+100;
const LL MOD = 1e9+7;
int nxt[MAX_N];
LL dp[MAX_N];
LL N[MAX_N];
char s1[MAX_N], s2[MAX_N];
int T;
void solve(){
cin >> s1 >> s2;
int n = strlen(s1), m = strlen(s2);
reverse(s1, s1+n);
reverse(s2, s2+m);
for(int i = 0; i <= m; ++i) dp[i] = 0;
int i = 0, j = nxt[0] = -1;
while(i < m){
while(j != -1 && s2[i] != s2[j]) j = nxt[j];
nxt[++i] = ++j;
}
for(i = 0, j = 0; i < n; ++i){
if(j < m && s1[i] == s2[j]){
dp[++j]++;
} else {
while(j > 0){
j = nxt[j];
if(s1[i] == s2[j]){
dp[++j]++;
break;
}
}
}
}
for(i = m; i >= 1; --i){
dp[nxt[i]] += dp[i];
}
LL ans = 0;
for(i = 1; i <= m; ++i){
ans = (ans + i * dp[i] % MOD) % MOD;
}
cout << ans << endl;
}
int main(){
// freopen("in.txt", "r", stdin);
ios::sync_with_stdio(0); cin.tie(0);
cin >> T;
while(T--) solve();
return 0;
}