CF 1466G Song of the Sirens
鸽了这么久，寒假集训强行水一波博客
xx.size()返回的是一个无类型，不能相减，定了天赋值到int上面warning一下，但是！！！一定不能做运算，不然就报RE,运算前一定要强制类型转换 调一年
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const long long mod=1e9+7;
int n,Q,k;
string t,w,temp;
long long p[N],two[N],f[27][N];
vector <string> s(1);
void get_kmp_init(string b)
{
int lb=b.size();
p[0]=0;
for(int i=1,j=0;i<lb;i++)
{
while(j>0 && b[i]!=b[j]) j=p[j-1];
if(b[i]==b[j]) j++;
p[i]=j;
}
return ;
}
int kmp(string a, string b)
{
//计算a中多少个b
int sum=0,la=a.size(),lb=b.size();
for(int i=0,j=0;i<la;i++)
{
while(j>0 && a[i]!=b[j])
j=p[j-1];
if(a[i]==b[j])
j++;
if(j==lb)
{
sum++;
j=p[j-1];
}
}
return sum;
}
long long pow3(long long x,long long y)
{
long long tempans=1;
while(y)
{
if(y%2!=0)
tempans=tempans*x%mod;
x=x*x%mod;
y>>=1;
}
return tempans;
}
int main()
{
cin>>n>>Q;
cin>>s[0]>>t;
two[0]=1;
for(int i=1;i<=n;i++)
two[i]=two[i-1]*2%mod;
for(int i=1;s[i-1].size()<1e6+3&&i<int(t.size())+1;i++)
{
s.push_back(s[i-1]+t[i-1]+s[i-1]);
}
//预处理第k层时字母j的总贡献的逆
for(int i=1;i<=n;i++)
{
for(int j=0;j<26;j++)
{
f[j][i]=f[j][i-1]%mod;
}
// if(i==1)
// {
// f[t[i-1]-'a'][i]=1;
// continue;
// }
long long temp=pow3(2,i)%mod;
f[t[i-1]-'a'][i]+=pow3(temp,mod-2);
f[t[i-1]-'a'][i]%=mod;
}
// for(int i=1;i<=n;i++)
// {
// printf("i:%d
",i);
// for(int j=0;j<26;j++)
// {
// printf("%d ",f[j][i]);
// }
// printf("
");
// }
for(int i=1;i<=Q;i++)
{
cin>>k>>w;
get_kmp_init(w);
long long ans=0;
bool flag=0;
for(int j=0;j<=k;j++)
{
if(j>0&&s[j-1].size()+1>=w.size())
{
//可以计算第二部分贡献时,枚举所有字母（去重后t中的字母也行）
for(int l=0;l<26;l++)
{
temp=s[j-1].substr(s[j-1].size()-w.size()+1)+(char)('a'+l)+s[j-1].substr(0,w.size()-1);
// cout<<j<<":"<<temp<<kmp(temp,w)<<endl;
ans+=(two[k]*(f[l][k]-f[l][j-1])%mod*kmp(temp,w)%mod)%mod;
ans%=mod;
}
break;
}
//必须放后面，不然贡献会算重复
if(s[j].size()>=w.size()&&flag==0)
{
// 第一次s.size()>w 计算第一部分贡献
ans+=two[k-j]*kmp(s[j],w)%mod;
flag=1;
}
}
printf("%lld
",(ans%mod+mod)%mod);
}
return 0;
}
/*
4 5
aba
bbac
3
3 3
aa
bcd
2 aba
3 ca
3 aa
*/