“强大的并不是你在顺境中能多么快的前进，而是你能多快在逆流中找回你自己”
俗称 $KMP$ 算法，用法是在一个字符串 $A$ 中快速地找到一个子串 $B$ 的出现情况。是AC自动机的组成部分之一。
对于引言，你是否有想法呢？
对于一个字符串，如果当我们匹配失败，我们是否需要重新开始匹配，还是说，我们能够仅仅往前一点，然后从这一个位置再次比配。对于 $KMP$ 而言，我们有一个定义称为失配数组。是对于该点如果没有匹配成功而跳回的位置，一般记作 nxt[] 或者 kmp[] 。看个人喜好。
实现
预处理
我们需要遍历子串 $B$ 以记录失配数组的失配情况。如果该点无法匹配，则从该点以 j=nxt[j] 往前跳，直到可以再次匹配为止。然后以这样的顺序处理出失配数组。
KMP 的实现是调整 $j$ 的位置（减小 $j$ 值）并使 $j$ 尽量大，使得 $A[i-j+1…i]$ 与 $B[1…j]$ 保持匹配且尝试匹配 $A[i+1]$ 和 $B[j+1]$ 。
匹配
遍历字符串 $A$ ，定义一个指针记为 $j$ 表示当前已经匹配到了第 $j$ 位。如果 $a[i] \neq b[j]$ ，则往前失配，直到再次匹配为止，如果 j=len(b) ，则证明我们已经匹配到了一个完整的子串 $B$ 。之后的操作就根据题目而定了。
例题
按上述实现即可，可能不太清楚，所以接下来给出代码。
这是没有改码风之前的代码，凑合着看吧。
AC Code
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
59
60
61
62
63
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
using std::cin;
using std::cout;
char stra[10000001],strb[10000001];
int Kmp[10000001],N,M,j;
int main()
{
cin>>(stra+1)>>(strb+1);
Kmp[1]=0;
N=strlen(strb+1);
M=strlen(stra+1);
for(int i=2;i<=N;++i)
{
while(j&&strb[i]!=strb[j+1])
{
j=Kmp[j];
}
if(strb[i]==strb[j+1])
{
++j;
}
Kmp[i]=j;
}
j=0;
for(int i=1;i<=M;++i)
{
while(j&&strb[j+1]!=stra[i])
{
j=Kmp[j];
}
if(stra[i]==strb[j+1])
{
++j;
}
if(j==N)
{
printf("%d\n",i-N+1);
}
}
for(int i=1;i<=N;++i)
{
printf("%d ",Kmp[i]);
}
return 0;
}
|
一道比较难的 $kmp$ 题，因为 $kmp$ 的思路其实与 $dp$ 差不多，所以一般而言两者是连在一起考的。用 f[i][j] 表示对于 $i$ 位数匹配到 $j$ 位的答案数，似乎有点像数位dp。预处理出 a[i][j] 表示从 f[x][i] 转移到 f[x+1][j] 的可能数。
那么转移方程则是 $dp_{i,j}=\sum\limits^{m-1}_{k=0}dp_{i-1,k}*a_{k,j}$ 即可。则答案便是 $\sum\limits_{i=0}^{m-1}dp_{n,i}$ 。但这样的话，时间复杂度是 $O(nm^2)$ ，对于这道题而言只能得到 $40pt$ 。
前置芝士：矩阵快速幂
将 $dp_{i,j}$ 记作矩阵 $DP_{i}$ ，$DP_{i}$ 的第一层就是 $dp_{i,j}$ 转移方程变成了 $DP_{i}=DP_{i-1}*G$ 然后求 $DP_n$ 即可。
AC Code
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=21;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int N,M,K;
int f[MAXN][MAXN];
char str[MAXN];
int Kmp[MAXN];
inline void underExpr(int c[][MAXN],int a[][MAXN],int b[][MAXN])
{
static int t[MAXN][MAXN];
memset(t,0,sizeof(t));
for(int i=0;i<M;++i)
for(int j=0;j<M;++j)
for(int k=0;k<M;++k)
t[i][j]=(t[i][j]+a[i][k]*b[k][j])%K;
for(int i=0;i<M;++i)
for(int j=0;j<M;++j)
c[i][j]=t[i][j];
}
inline int underQuickPow(int k)
{
int f0[MAXN][MAXN]={1};
while(k)
{
if(k&1) underExpr(f0,f0,f);
underExpr(f,f,f);
k>>=1;
}
int res=0;
for(int i=0;i<M;++i) res=(res+f0[0][i])%K;
return res;
}
int main()
{
underRead(N),underRead(M),underRead(K);
scanf("%s",str+1);
for(int i=2,j=0;i<=M;++i)
{
while(j&&str[j+1]!=str[i]) j=Kmp[j];
if(str[j+1]==str[i])++j;
Kmp[i]=j;
}
for(int j=0;j<M;++j)
for(int c='0';c<='9';++c)
{
int k=j;
while(k&&str[k+1]!=c) k=Kmp[k];
if(str[k+1]==c) ++k;
if(k<M) ++f[j][k];
}
printf("%d",underQuickPow(N));
return 0;
}
|