旅游网站规划说明,网站图片延时加载,排名前十的大学,wordpress网站无法登陆题目大意#xff1a;给你两个字符串A,B#xff0c;现在要你求B串的后缀在A串中出现的次数和后缀长度的乘积和为多少。题解#xff1a;扩展KMP模板题#xff0c;将A和B串都逆序以后就变成了求前缀的问题了#xff0c;扩展KMP求处从i位置开始的最长公共前缀存于数组。最后通…题目大意 给你两个字符串A,B现在要你求B串的后缀在A串中出现的次数和后缀长度的乘积和为多少。 题解 扩展KMP模板题将A和B串都逆序以后就变成了求前缀的问题了扩展KMP求处从i位置开始的最长公共前缀存于数组。 最后通过将数组的值不为0的进行一个桶计数倒着进行一下求和就可以了。注意在这个题目上扩展kmp处理出来的是 ex[ i ]数组是 A串的每个从 i 位置开始的后缀 与B串的最长公共前缀长度那么这样B串在A串上匹配的情况就一目了然了。 #includebits/stdc.h
using namespace std;
const int mod1e97;
const int N 1000005;
int Next[N];
long long ex[N],tong[N]; //即extand[]
char p[N],t[N];
int T;
long long ans;
void pre() // next[i]: 以第i位置开始的子串 与 T的公共前缀
{int lpstrlen(p);Next[0]lp;int j0,k1;while(j1lp p[j]p[j1]) j;Next[1]j;for(int i2; ilp; i){int PNext[k]k-1;int LNext[i-k];if(iLP1) Next[i]L;else{jmax(0,P-i1);while(ijlp p[ij]p[j]) j; // 枚举(p1length) 与(p-k1,length) 区间比较Next[i]j;ki;}}
}
void exkmp()
{int lpstrlen(p),ltstrlen(t);pre(); //next数组初始化int j0,k0;while(jlt jlp p[j]t[j]) j;ex[0]j;for(int i1; ilt; i){int Pex[k]k-1;int LNext[i-k];if(iLP1) ex[i]L;else{jmax(0,P-i1);while(ijlt jlp t[ij]p[j]) j;ex[i]j;ki;}}
}
int main()
{scanf(%d,T);while(T--){memset(tong,0,sizeof(tong));scanf(%s%s,t,p);int ltstrlen(t);int lpstrlen(p);reverse(p,plp);reverse(t,tlt);exkmp();ans0;for(int i0; ilt; i)tong[ex[i]];for(int ilp;i;i--){tong[i](tong[i]tong[i1])%mod;ans(anstong[i]*i%mod)%mod;}printf(%lld\n,ans);}
}转载于:https://www.cnblogs.com/SDUTNING/p/10388792.html
