Luogu 3375
Luogu 3375
KMP算法，准确的说是KM算法，遥想很久以前写过一次，后来就再也没有动过了。现在差不多也已经忘记怎么写了，重新学习以下。
例题是Luogu上的一道模板题，以前做过一次，只得了70分。这次又做了一遍，结果我已经无力吐槽了。用
gets()读入字符串0分，自己用getchar()手写读入是70分，用scanf()读入是100分。。。。。纠结了我一整个下午的问题就这么解决了○|￣|_
题目来源:Luogu
考虑字符串a(长度\(n\)),b(长度\(m\)),\(m<=n\),传统的字符串匹配算法的时间复杂度是\(O(mn)\)的(极端情况下),而Kmp的时间复杂度是\(O(m+n)\)。其关键在于其前缀数组。
我们在使用传统的字符串匹配算法时，极端情况下之所以很慢，是因为我们可能会将两个字符串中的每一个字符都比较一遍。但是在很多情况下，我们知道了字符串b后，当我们与字符串a匹配失败后，我们可以显然的到向右移动一位甚至好几位之后还是无法匹配的。KMP算法就是通过预处理，算出在当前匹配失败后，b向右移动多少位才有可能匹配，从而节省时间。
这样，我们可以通过一个数组f[i]来记录右移后第几个字符能够到达i的位置。在匹配过程中，代码如下： 1
2
3
4
5
6
7
8
9
10
11
12
13int j = 0;
for (int i = 0; i<n; i++)
{
while (j && a[i]!=b[j])
j = f[j];
if (a[i]==b[j])
j++;
if (j==m)
{
printf("%d",i-m+1);
break;
}
}
而整个算法中，最为神(xuan)奇(xue)的就是失配函数f[]的构造，其实也就是一个b数组对自己进行匹配的过程: 1
2
3
4
5
6
7for (int i = 0; i<m; i++)
{
trueint j = f[i];
while (j && b[i]!=b[j])
j = f[j];
f[i+1] = b[i]==b[j]?1:0;
}
注意：上面我们求的
f[i]满足的条件为\(b[f[i]-1] == b[i-1]\)而非\(b[f[i]] == b[i]\)，而下列代码中的f[i]由于题目要求，满足的条件为\(b[f[i]-1] == b[i]\).
代码: 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
char a[MAXN],b[MAXN];
int f[MAXN];
int n,m;
/*
void GetString(char* s,int& n)
{
char c = getchar();
while ((c<'A'||c>'Z') && (c<'a'||c>'z'))
c = getchar();
n = 0;
while ((c>='A'&&c<='Z')||(c>='a'&&c<='z'))
{
s[n++] = c;
c = getchar();
}
return;
}
*/
void getFail()
{
truef[0] = 0;
true//f[1] = 0;
truefor (int i = 1; i<m; i++)
true{
truetrueint j = f[i-1];
truetruewhile (j && b[i]!=b[j]) j = f[j-1];
truetruef[i] = b[i]==b[j]?j+1:0;
true}
truereturn;
}
void find()
{
trueint j = 0;
truefor (int i = 0; i<n; i++)
true{
truetruewhile (a[i]!=b[j] && j) j = f[j-1];
truetrueif (a[i]==b[j]) j++;
truetrueif (j==m)
truetruetrueprintf("%d\n",i-m+2);
true}
}
int main()
{
true//GetString(a,n);
true//GetString(b,m);
truescanf("%s",a);
truescanf("%s",b);
true//gets(a);
truen = strlen(a);
true//gets(b);
truem = strlen(b);
truegetFail();
truefind();
truefor (int i = 0; i<m; i++)
truetrueprintf("%d ",f[i]);
}