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
| #include <cstdio>
#include <cstring>
int T, p[10001];
char w[10001], t[1000001];
int main()
{
scanf("%d", &T);
for(; T; --T)
{
scanf("%sn%s", w, t);
int lw = strlen(w), lt = strlen(t), ans = 0;
p[0] = -1;
for (int i = 1, j = -1; i < lw; ++i)
{
for (; j > -1 && w[i] != w[j+1]; j = p[j]);
if (w[i] == w[j+1]) ++j;
p[i] = j;
}
for (int i = 0, j = -1; i < lt; ++i)
{
for (; j > -1 && t[i] != w[j+1]; j = p[j]);
if (t[i] == w[j+1]) ++j;
if (j == lw-1)
{
++ans;
j = p[j];
}
}
printf("%dn", ans);
}
}
|
