BNU 13174 Substring Frequency

3C. Substring Frequency

Time Limit: 1000ms

Memory Limit: 32768KB

64-bit integer IO format: %lld Java class name: Main

A string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given two non-empty strings Aand B, both contain lower case English characters. You have to find the number of times B occurs as a substring of A.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with two lines. First line contains A and second line contains B. You can assume than 1 ≤ length(A), length(B) ≤ 106.

Output

For each case, print the case number and the number of times B occurs as a substring of A.

Sample Input

axbyczd

abc

abcabcabcabc

abc

aabacbaabbaaz

aab

aaaaaa

Sample Output

Case 1: 0

Case 2: 4

Case 3: 2

Case 4: 5

解题：裸KMP的使用。。。。。。。。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #define LL long long
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 int fail[1000010];
16 char str[1000020],p[1000010];
17 void getFail(int &len){
18     fail[0] = fail[1] = 0;
19     len = strlen(p);
20     for(int i = 1; i < len; i++){
21         int j = fail[i];
22         while(j && p[i] != p[j]) j = fail[j];
23         fail[i+1] = p[i] == p[j]?j+1:0;
24     }
25 }
26 int main(){
27     int t,i,j,len,ans,k = 1;
28     scanf("%d",&t);
29     while(t--){
30         scanf("%s%s",str,p);
31         getFail(len);
32         j = ans = 0;
33         for(i = 0; str[i]; i++){
34             while(j && str[i] != p[j]) j = fail[j];
35             if(str[i] == p[j]) j++;
36             if(j == len) ans++;
37         }
38         printf("Case %d: %d
",k++,ans);
39     }
40     return 0;
41 }

View Code