·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=3461
这题是KMP算法模板题。直接贴上KMP模板。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
const int maxn = 1e6+10; //需要注意的是这里的1e6+10以及下一行的1e4+10是double类型，不过经过类型强转后仍然可用
const int maxm = 1e4+10;
char word[maxm], text[maxn];
int nxt[maxm];
void getnxt(char *P, int *f) {
int m = strlen(P) - 1; //主函数中使用了fgets，字符串的最后一位是回车
f[0] = 0; f[1] = 0;
for (int i = 1; i < m; i++) {
int j = f[i];
while (j && P[i]!=P[j]) j = f[j];
f[i+1] = P[i] == P[j] ? j+1 : 0;
}
}
int kmp(char *T, char *P, int *f) {
int n = strlen(T) - 1, m = strlen(P) - 1; //去掉字符串最后一位的回车
int ans = 0;
getnxt(P, f);
int j = 0;
for (int i = 0; i < n; i++) {
while (j && P[j]!=T[i]) j = f[j];
if (P[j] == T[i]) j++;
if (j == m) ans++;
}
return ans;
}
int main() {
int cas = 0;
int cnt = 0;
scanf("%d%*c", &cas);
while (cas--) {
fgets(word, maxm, stdin);
fgets(text, maxn, stdin);
memset(nxt, 0, sizeof(nxt));
cnt = kmp(text, word, nxt);
printf("%d\n", cnt);
}
}