forked from gitter-badger/Interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathp1015.cpp
More file actions
40 lines (36 loc) · 790 Bytes
/
p1015.cpp
File metadata and controls
40 lines (36 loc) · 790 Bytes
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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
const int maxn = 1001000;
char str[maxn], buf[maxn];
int nxt[10100];
void get_next() {
for (int i = 1, j = 0; str[i]; i++) {
while (j && str[j] != str[i])
j = nxt[j-1];
nxt[i] = j += (str[j] == str[i]);
}
}
int solve() {
int cnt = 0;
for (int i = 0, j = 0; buf[i]; i++) {
while (j && str[j] != buf[i])
j = nxt[j-1];
j += (str[j] == buf[i]);
if (j == strlen(str))
cnt++;
}
return cnt;
}
int main() {
int test;
scanf("%d", &test);
for (int cas = 1; cas <= test; cas++) {
scanf("%s %s", str, buf);
get_next();
printf("%d\n", solve());
}
return 0;
}