hdu 6153 A Secret(KMP)

题意：

给你两个字符串a,b，问你对于b的每个后缀在a中出现了多少次，然后输出sum{每个后缀的长度*该后缀在a中出现的次数}。

题解：

将a,b反转一下，然后跑一下kmp，在途中记录一下哪些位置匹配到了。

然后再倒着统计一下答案就行了。

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=1e6+7,P=1e9+7;
 7 int t,lena,lenb,nxt[N],vis[N],ans[N];
 8 char a[N],b[N];
 9 
10 void KMP(int n, char*a, int m, char*b) {
11     int i, j;
12     for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {
13         while (~j&&a[j + 1] != a[i])j = nxt[j];
14         if (a[j + 1] == a[i])j++;
15     }
16     for (j = -1, i = 0; i < m; i++) {
17         while (~j&&a[j + 1] != b[i])j = nxt[j];
18         if (a[j + 1] == b[i])j++;
19         if(j!=-1)vis[j]++;
20         if (j == n - 1)j = nxt[j];
21     }
22 }
23 
24 int main(){
25     scanf("%d",&t);
26     while(t--)
27     {
28         mst(vis,0),mst(ans,0),scanf("%s%s",a,b);
29         lena=strlen(a),lenb=strlen(b);
30         reverse(a,a+lena);
31         reverse(b,b+lenb);
32         KMP(lenb,b,lena,a);
33         for(int i=lenb;i;i--)
34         {
35             ans[i]+=vis[i-1];
36             if(nxt[i-1]!=-1)ans[nxt[i-1]+1]+=ans[i];
37         }
38         int ret=0;
39         F(i,1,lenb)ret=(ret+(ll)i*ans[i])%P;
40         printf("%d
",ret);
41     }
42     return 0;
43 
44 }

View Code