P3375-【模板】KMP字符串匹配
题目:
题目描述:
如题，给出两个字符串 $s_1$ 和 $s_2$，其中 $s_2$ 为 $s_1$ 的子串，求出 $s_2$ 在 $s_1$ 中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组 next。
（如果你不知道这是什么意思也不要问，去百度搜 kmp算法 学习一下就知道了。）
输入格式:
第一行为一个字符串，即为 $s_1$。
第二行为一个字符串，即为 $s_2$。
输出格式:
若干行，每行包含一个整数，表示 $s_2$ 在 $s_1$ 中出现的位置
接下来 $1$ 行，包括 $|s2|$ 个整数，表示前缀数组 $next_i$ 的值。
样例:
样例输入1:
样例输出1:
思路:
实现:
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
| #include "ybwhead/ios.h"
const int maxn = 1e6 + 10;
char s1[maxn], s2[maxn];
int kmp[maxn];
int main()
{
cin >> (s1 + 1) >> (s2 + 1);
int n = strlen(s1 + 1), m = strlen(s2 + 1);
int j = 0;
for (int i = 2; i <= m; i++)
{
while (j && s2[j + 1] != s2[i])
j = kmp[j];
if (s2[j + 1] == s2[i])
++j;
kmp[i] = j;
}
j = 0;
for (int i = 1; i <= n; i++)
{
while (j && s2[j + 1] != s1[i])
j = kmp[j];
if (s2[j + 1] == s1[i])
++j;
if (j == m)
{
yout << i - m + 1 << endl;
j = kmp[j];
}
}
for (int i = 1; i <= m; i++)
{
yout << kmp[i] << " ";
}
return 0;
}
|