题目点我
题目:A Secret
题意:给两个字符串S!, S2, S2的所有后缀的权重是它本身的长度, 问他所有后缀在S1中总贡献(每个后缀出现次数*权重之和).
思路:典型的kmp模式匹配, 可以把S1和S2倒过来, 运用膜板。 与模板不同的是求的东西不一样。但是可以确定的是可以通过修改模板得到结果。
原因是：题目所要得到的所有数据都可以在KMP的匹配过程中求得， 遍历了KMP的过程， 也就遍历了所需要的所有数据。比如说，每个后缀的
权重（长度）可以通过S2模式串的预处理得到， 每个后缀出现的次数可以在KMP匹配过程中进行记录。
此外，我们还可以发现一个重要性质：当长度为i的模式（后缀？前缀？）与模板匹配后， 长度为i-1的模式也一定已经匹配了， 这样我们就
不需要每匹配一个字符就计算一次贡献了，而是当适配的时候把前面的贡献一次性算出来（当然再扫一遍S2计算贡献肯定是不明智的），我们
可以通过前缀和等等的方式O(1)直接取出贡献的.具体情况还是看一下代码吧:
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod=1e9+7.2;
const int maxn=1e6+100;
int f[maxn], val[maxn], n, m;//f->失配数组, val[i]->当在i失配时, 长度为1,2,...,i的模式串增加的贡献
char s1[maxn], s2[maxn], ss[maxn];
void getFail_pro(char *P, int *f, int m){
f[0]=f[1]=0; val[0]=0;
for (int i=1, j=0; i<m; i++){//i一定是到m-1的, f[m]也是合法并且需要的
val[i]=(val[i-1]+i)%mod;//显然的前缀递推
j=f[i];
while (j&&P[i]!=P[j]) j=f[j];
f[i+1]= P[i]==P[j]? j+1 : 0;
}
val[m]=(val[m-1]+m)%mod;//这个不能丢
}
int find(char* T, char* P, int *f, int n, int m){
getFail_pro(P, f, m);
int j=0;
LL ans=0;
for (int i=0; i<n; i++){
while ((j && P[j]!=T[i])) {
ans=(ans+val[j])%mod;//失配时算贡献, 另外当j==m时一定会发生失配
j=f[j];
}
if (P[j]==T[i]) j++;
}
while (j>0){//这个也一定不能少, 因为我们是用模式串算贡献的,所以模式串没到0之前一定会有已经匹配了但还没算贡献的子模式
ans=(ans+val[j])%mod;
j=f[j];
}
return ans%mod;
}
int main(void){
int T;
for (scanf("%d", &T); T; T--){
scanf("%s", ss);
n=strlen(ss);
for (int i=0; i<n; i++){
s1[i]=ss[n-i-1];
}
s1[n]=0;
scanf("%s", ss);
m=strlen(ss);
for (int i=0; i<m; i++){
s2[i]=ss[m-i-1];
}
s2[m]=0;
printf("%d\n", find(s1, s2, f, n, m));
}
return 0;
}