ASecret(KMP+后缀和)

给出两个字符串, 统计串2的后缀子串在串1中的出现次数. 假设串2中后缀子串长度为i时在串1中出现x次, 则fact(s2, i) &＃61; i * x. 最终输出 fact(s2, i)的总和(1 <&＃61; i <&＃61; |s2|) .

题目感觉不太好叙述, 麻烦自己看吧

解题思路:

对于字符串匹配, 我们很容易想到kmp, 但是kmp的匹配和这个题的思路有些不同, kmp是计算前缀, 而本题则是计算后缀. 所以我们不妨将s1与s2都进行翻转, 这样我们就可以得到kmp的模板串s1, 模式串s2.

现在我们发现, 在我们进行kmp时, 如果匹配到第j位失败(第j-1位成功匹配), 则s2的[1, j - 1]区间的前缀子串匹配的长度都应当&＃43;1. 这样我们发现, 我们可以通过后缀和优化, 从而在线性时间内得出结果.

AC代码:

#include
using namespace std;
typedef long long ll;
const int N &＃61; 1E6 &＃43; 10, mod &＃61; 1E9 &＃43; 7;
char s1[N], s2[N];
int ne[N], cou[N]; //起初cou数组为以第i位匹配成功, i&＃43;1匹配失败时的情况数量
int main()
{int t; cin >> t;while (t--) {memset(cou, 0, sizeof cou);scanf("%s %s", s1 &＃43; 1, s2 &＃43; 1); int l1 &＃61; strlen(s1 &＃43; 1), l2 &＃61; strlen(s2 &＃43; 1);reverse(s1 &＃43; 1, s1 &＃43; 1 &＃43; l1); reverse(s2 &＃43; 1, s2 &＃43; 1 &＃43; l2); for (int i &＃61; 2, j &＃61; 0; i <&＃61; l2; &＃43;&＃43;i) { //kmp处理ne数组while (j && s2[i] !&＃61; s2[j &＃43; 1]) j &＃61; ne[j];if (s2[i] &＃61;&＃61; s2[j &＃43; 1]) &＃43;&＃43;j;ne[i] &＃61; j;}/* KMP */int j &＃61; 0;for (int i &＃61; 1; i <&＃61; l1; &＃43;&＃43;i) {while (j && s1[i] !&＃61; s2[j &＃43; 1]) cou[j]&＃43;&＃43;, j &＃61; ne[j]; //匹配到j成功, j&＃43;1失败, 记录情况if (s1[i] &＃61;&＃61; s2[j &＃43; 1]) &＃43;&＃43;j;}while (j) cou[j]&＃43;&＃43;, j &＃61; ne[j]; //收尾操作, 很重要//求后缀和, 此时cou数组性质改变为串s2中长度为i的前缀子串匹配次数.for (int i &＃61; l2 - 1; i >&＃61; 1; --i) cou[i] &＃43;&＃61; cou[i &＃43; 1]; int res &＃61; 0; //计算resfor (int i &＃61; 1; i <&＃61; l2; &＃43;&＃43;i) res &＃61; (res &＃43; 1ll * cou[i] * i) % mod;printf("%d\n", res);}return 0;
}


END