正解是trie树。。。在树上跳来跳去什么的
然而在企鹅qq那题的影响下我写了hash。。。
添加一个字母到一个串，就相当于另一个串删对应位置上的字母。
改变某个位置上的字母，就相当于两个字符串删掉同一个位置上的字母。
所以要记录的东西也不多。。存一下每个串删掉每个位置上的字母后的hash值并排序，然后查询的时候二分一下就行了。
但要注意的是，两个字符串可能有多种编辑方式。。。比方说字符串cccc，分别删掉四个位置上的字母后得到的都是ccc。。
所以一开始要再去一下重。（要不是老司机提醒我还不知道要调多久TAT
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ull unsigned long long
using namespace std;
const int maxn=;
ull mp[][maxn];
ull b[],jc[],pre[];
ull map[*maxn];
int len[maxn],num[];
int i,j,k,n,m,l,r,mid,cnt,ans;
char s[];
inline int getl(int x,ull v){
for(l=,r=num[x];l<r;)
if(mp[x][mid=(l+r)>>]<v)l=mid+;else r=mid;
return mp[x][l]==v?l:;
}
inline int getr(int x,ull v){
for(l=,r=num[x];l<r;)
if(mp[x][mid=(l+r+)>>]<=v)l=mid;else r=mid-;
return mp[x][l]==v?l:;
}
inline int get(int ull v){
int posl;
for(l=,r=cnt;l<r;)
if(map[mid=(l+r)>>]<v)l=mid+;else r=mid;
if(map[l]!=v)return ;
if(map[l+]!=v)return ;
posl=l;
for(l=posl,r=cnt;l<r;)
if(map[mid=(l+r+)>>]<=v)l=mid;else r=mid-;
return l-posl+;
}
int main(){
register int j;
scanf("%d%d",&n,&m);
for(i=jc[]=;i<=;i++)jc[i]=jc[i-]*;
int mx=;num[]=n;
for(i=;i<=n;i++){
scanf("%s",s);len[i]=strlen(s);
for(j=;j<=len[i];j++)pre[j]=pre[j-]*+s[j-];
for(j=;j<=len[i];j++)
mp[j][++num[j]]=pre[len[i]]-pre[j]*jc[len[i]-j]+pre[j-]*jc[len[i]-j];
mp[][i]=pre[len[i]];
mx=max(mx,len[i]);
for(j=;j<=len[i];j++)b[j]=mp[j][num[j]];
sort(b+,b++len[i]);
for(j=len[i];j;j--)if(j==len[i]||b[j+]!=b[j])map[++cnt]=b[j];//,printf(" %lld\n",b[j]);
// printf("! %lld\n",mp[1][num[1]]);
}
for(i=;i<=mx;i++)sort(mp[i]+,mp[i]++num[i]);
sort(map+,map++cnt);
// for(i=0;i<=mx;i++){
// for(j=1;j<=num[i];j++)printf(" %lld",mp[i][j]);puts("");
// }
ull tmp;
while(m--){
scanf("%s",s);int len=strlen(s);
for(j=;j<=len;j++)pre[j]=pre[j-]*+s[j-];
if((k=getl(,pre[len]))){puts("-1");continue;} ans=get(pre[len]);//printf(" %d\n",ans);
for(j=;j<=len;j++){
tmp=b[j]=pre[len]-pre[j]*jc[len-j]+pre[j-]*jc[len-j];
if((k=getl(j,tmp)))ans+=getr(j,tmp)-k+;
} sort(b+,b++len);
for(j=len;j;j--)
if(j==len||b[j+]!=b[j])
if((k=getl(,b[j])))
ans+=getr(,b[j])-k+; printf("%d\n",ans);
}
return ;
}