首页 > 代码库 > BNU 13174 Substring Frequency

BNU 13174 Substring Frequency

2024-07-14 07:21:00   221人阅读

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

4

axbyczd

abc

abcabcabcabc

abc

aabacbaabbaaz

aab

aaaaaa

aa

 

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 long13 #define INF 0x3f3f3f3f14 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\n",k++,ans);39     }40     return 0;41 }
View Code

 


联系
我们