[HDOJ6153] A Secret（kmp, 计数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6153

题意：给两个字符串s1, s2。问s2的所有后缀在s1中出现次数*后缀长度的和。

两个字符串反过来，s2预处理个pre数组，在对s1跑kmp。失配的时候记录下这个长度len，代表1~len这么多个后缀已经匹配到。

注意匹配结束后，一定要顺着pre数组更新贡献。

最后结果(1+i)*i/2*vis(i)，取模的话，2对1e9+7的逆元是500000004。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define lson l, m, rt << 1
 5 #define rson m + 1, r, rt << 1 | 1
 6 typedef long long LL;
 7 const LL mod = 1e9+7;
 8 const int maxn = 1001000;
 9 int na, nb;
10 char a[maxn];
11 char b[maxn];
12 int pre[maxn];
13 LL vis[maxn];
14 
15 
16 void getpre(char *b, int *pre) {
17     int j, k;
18     pre[0] = -1;
19     j = 0; k = -1;
20     while(j < nb) {
21         if(k == -1 || b[j] == b[k]) {
22             j++; k++;
23             pre[j] = k;
24         }
25         else k = pre[k];
26     }
27 }
28 
29 void kmp() {
30     int ans = 0;
31     int i = 0, j = 0;
32     getpre(b, pre);
33     while(i < na) {
34         if(j == -1 || a[i] == b[j]) {
35             i++; j++;
36         }
37         else {
38             vis[j]++;
39             j = pre[j];
40         }
41         if(j == nb) continue;
42     }
43     while(j != -1) {
44         vis[j]++;
45         j = pre[j];
46     }
47 }
48 
49 signed main() {
50     // freopen("in", "r", stdin);
51     int T;
52     scanf("%d", &T);
53     while(T--) {
54         scanf("%s%s",a,b);
55         memset(vis, 0, sizeof(vis));
56         LL ret = 0;
57         na = strlen(a); nb = strlen(b);
58         reverse(a, a+na); reverse(b, b+nb);
59         kmp();
60         for(LL i = 1; i <= nb; i++) {
61             LL tmp = i * (1LL + i) % mod;
62             tmp *= vis[i];
63             tmp %= mod;
64             tmp *= 500000004LL;
65             tmp %= mod;
66             ret += tmp;
67             ret %= mod;
68         }
69         printf("%lld
", ret);
70     }
71     return 0;
72 }