首页 > 代码库 > xtu字符串 C. Marlon's String

xtu字符串 C. Marlon's String

2024-07-14 20:25:59   225人阅读

C. Marlon‘s String

Time Limit: 2000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld      Java class name: Main
 
 

Long long ago, there was a coder named Marlon. One day he picked two string on the street. A problem suddenly crash his brain...

Let Si..j denote the i-th character to the j-th character of string S.

Given two strings S and T. Return the amount of tetrad (a,b,c,d) which satisfy Sa..b + Sc..d = T , a≤b and c≤d.

The operator + means concate the two strings into one.

Input

The first line of the data is an integer Tc. Following Tc test cases, each contains two line. The first line is S. The second line is T. The length of S and T are both in range [1,100000]. There are only letters in string S and T.

Output

For each test cases, output a line for the result.

Sample Input

1aaabbbab

Sample Output

9

解题：与扩展KMP无关，与前缀有关。。。直接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[100010];16 char pa[100010],s[100010];17 int a[100010],b[100010];18 void kmp(int *arr){19     int i,j,k;20     fail[0] = fail[1] = 0;21     for(i = 1; pa[i]; i++){22         j = fail[i];23         while(j && pa[i] != pa[j]) j = fail[j];24         fail[i+1] = pa[j] == pa[i] ? j+1:0;25     }26     for(j = i = 0; s[i]; i++){27         while(j && s[i] != pa[j]) j = fail[j];28         if(pa[j] == s[i]){29             arr[++j]++;30         }31     }32     for(i = strlen(pa); i >= 0; i--)33         if(fail[i]) arr[fail[i]] += arr[i];34 }35 int main(){36     int t,i,len;37     LL ans;38     scanf("%d",&t);39     while(t--){40         scanf("%s %s",s,pa);41         memset(a,0,sizeof(a));42         memset(b,0,sizeof(b));43         kmp(a);44         reverse(s,s+strlen(s));45         reverse(pa,pa+strlen(pa));46         kmp(b);47         ans = 0;48         for(len = strlen(pa),i = 0; i < len; i++)49             ans += (LL)a[i]*b[len-i];50         printf("%lld\n",ans);51     }52     return 0;53 }
View Code

 


联系
我们