字符串匹配
字符串匹配
Code[VS] 1404
本来以为是一个标准的KMP模板题，结果写着写着才发现这道题的重点在别处。用到了KMP算法，但是最重要的还是考验思维能力。
题目来源: code[VS]
分析
题目要求对于给定的x，输出字符串b在字符串a中匹配长度恰为x的数目。这道题我本来时打算当作KMP的模板题来做，于是我就先写好了KMP算法，然后准备在其基础上更改。
KMP算法写好后，我们首先可以想到的是失配时，此时满足题目的条件。我们可以在KMP匹配时使用一个数组ans[i]来记录匹配长度恰为i的数量。所以，我们可以将匹配常数更改如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void KMP()
{
trueint j = 0;
truefor (int i = 0; i<a.length(); i++)
true{
truetruewhile (j && a[i]!=b[j])
truetrue{
truetruetrueans[j] ++;
truetruetruej = fail[j];
truetrue}
truetrueif (a[i]==b[j])
truetruetruej++;
true}
}
|
我们进一步思考，会发现\(j==0\)时会无法执行ans[j]++操作，所以可以在if语句前加上一句
1
2
| if (a[i]!=b[0])
trueans[0]++;
|
此外，我们发现并不是所有的恰好长度的匹配都会被我们发现，譬如当我们匹配ababcc(字符串a)和ababc(字符串b)时，我们应该能够匹配到a串的第3,4个字符与b串的前两个字符，然后ans[2]++。但是实际上因为ababcc的前五个字符都与b串匹配，所以我们无法通过失配函数回到b串只走了两个字符的情况。所以我们还可以加上一下代码来匹配所有长度：
1
2
3
4
5
6
7
| int k = j;
while (k)
{
if (b[k]!=a[i])
ans[k]++;
k = fail[k];
}
|
最后，我们发现匹配结束时需要特殊处理，否则可能会漏掉两个字符串最后一个字符相同的情况。所以说在KMP匹配的for循环后需要加上如下几句：
1
2
3
4
5
| while (j)
{
ans[j]++;
j = fail[j];
}
|
完成了以上几步后，代码便大致完成了，然而，由于多嵌套了一个while循环，所以最后T了两组数据，代码如下。
80分代码（TLE）
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
| #include <iostream>
#include <string>
using namespace std;
int ans[200100];
int fail[200100];
int cnt[200100];
string a,b;
void pre()
{
for (int i = 1; i<b.length(); i++)
{
int j = fail[i];
while (j && b[i]!=b[j])
j = fail[j];
fail[i+1] = b[i]==b[j]?j+1:0;
}
}
void KMP()
{
int j = 0;
for (int i = 0; i<a.length(); i++)
{
if (j==b.length())
{
ans[j]++;
j = fail[j];
}
while (j && a[i]!=b[j])
{
ans[j] ++;
j = fail[j];
}
int k = j;
while (k)
{
if (b[k]!=a[i])
ans[k]++;
k = fail[k];
}
if (a[i]!=b[0])
ans[0]++;
if (a[i]==b[j])
j++;
}
while (j)
{
ans[j]++;
j = fail[j];
}
}
int main()
{
ios::sync_with_stdio(false);
int n,m,k;
cin >> n >> m >> k;
cin >> a;
cin >> b;
pre();
KMP();
while (k--)
{
int x;
cin >> x;
cout << ans[x] << endl;
}
}
|
进一步分析
很明显，之前的算法由于需要嵌套循环，时间复杂度为O(nm),无论如何优化也是不行的。所以，我们应该换一个思路。
我们可以想到，对于一个可以匹配的长度为k的串，它存在两种情况：其最长便只能匹配k;其还可以向后匹配。而我们想求出的是第一种情况，但是直接求解显然非常复杂。但是如果我们有两种情况的数量总和呢？我们能不能很简单的算出第一种情况呢？
很明显，假设num[]存储了能匹配长度k的情况的数量，ans[]为能且恰好匹配了长度k的情况的数量,那么其一定满足下面的公式：
\[ ans_i = num_i - num_{i+1} \]
得到了上面的公式，我们便能够把能够匹配长度为k的情况一股脑地加载一起就好了，譬如，在KMP函数中，代码如下：
1
2
3
4
5
6
7
8
9
10
| int j = 0;
for (int i = 0; i<a.length(); i++)
{
truewhile (j && a[i]!=b[j])
truetruej = fail[j];
trueif (a[i]==b[j])
truetruej++;
trueans[j] ++;
}
|
而很明显上面并不是全部的情况。譬如我们之前举的ababcc与ababc的例子。很明显，当我们考虑的是所有大于k的情况是，我们可以令所有的\(num_{fail_i} = num_{fail_i} + num_i\)。所以在主函数里，KMP函数执行后，加入如下代码：
1
2
| for (int i = 0; i<b.length(); i++)
trueans[i] -= ans[i+1];
|
最后，代码便大致完成了，最终AC代码如下：
AC代码
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
|
#include <iostream>
#include <string>
using namespace std;
int ans[200100];
int fail[200100];
bool flag[200100];
string a,b;
void pre()
{
truefor (int i = 1; i<b.length(); i++)
true{
truetrueint j = fail[i];
truetruewhile (j && b[i]!=b[j])
truetruetruej = fail[j];
truetruefail[i+1] = b[i]==b[j]?j+1:0;
true}
}
void KMP()
{
trueint j = 0;
truefor (int i = 0; i<a.length(); i++)
true{
truetruewhile (j && a[i]!=b[j])
truetruetruej = fail[j];
truetrueif (a[i]==b[j])
truetruetruej++;
truetrueans[j] ++;
true}
}
int main()
{
trueint n,m,k;
truecin >> n >> m >> k;
truecin >> a;
truecin >> b;
truepre();
trueKMP();
truefor (int i = b.length(); i>0; i--)
truetrueans[fail[i]] += ans[i];
truefor (int i = 0; i<b.length(); i++)
truetrueans[i] -= ans[i+1];
truewhile (k--)
true{
truetrueint x;
truetruecin >> x;
truetruecout << ans[x] << endl;
true}
}
|