原理就不赘述了，忘记了就去看《大话数据结构》。
给定模式串 S 以及模板串 P ，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
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
| #include <cstdio>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char s[M], p[N];
int next[N];
int main()
{
int n, m;
scanf("%d%s%d%s", &n, p + 1, &m, s + 1);
for(int i = 2, j = 0; i <= n; ++i)
{
while(j && p[i] != p[j + 1]) j = next[j];
if(p[i] == p[j + 1]) ++j;
next[i] = j;
}
for(int i = 1, j = 0; i <= m; ++i)
{
while(j && s[i] != p[j + 1]) j = next[j];
if(s[i] == p[j + 1]) ++j;
if(j == n)
{
printf("%d ", i - n);
j = next[j];
}
}
return 0;
}
|