正解是trie树。。。在树上跳来跳去什么的

　　然而在企鹅qq那题的影响下我写了hash。。。

　　添加一个字母到一个串，就相当于另一个串删对应位置上的字母。

　　改变某个位置上的字母，就相当于两个字符串删掉同一个位置上的字母。

　　所以要记录的东西也不多。。存一下每个串删掉每个位置上的字母后的hash值并排序，然后查询的时候二分一下就行了。

　　但要注意的是，两个字符串可能有多种编辑方式。。。比方说字符串cccc，分别删掉四个位置上的字母后得到的都是ccc。。

　　所以一开始要再去一下重。（要不是老司机提醒我还不知道要调多久TAT

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define ull unsigned long long 6 using namespace std; 7 const int maxn=10023; 8 ull mp[21][maxn]; 9 ull b[21],jc[21],pre[21];10 ull map[20*maxn];11 int len[maxn],num[21];12 int i,j,k,n,m,l,r,mid,cnt,ans;13 char s[23];14 inline int getl(int x,ull v){15     for(l=1,r=num[x];l
          
           >1]
           
            >1]<=v)l=mid;else r=mid-1;22 return mp[x][l]==v?l:0;23 }24 inline int get(int ull v){25 int posl;26 for(l=1,r=cnt;l
            
             >1]
             
              >1]<=v)l=mid;else r=mid-1;33 return l-posl+1;34 }35 int main(){36 register int j;37 scanf("%d%d",&n,&m);38 for(i=jc[0]=1;i<=20;i++)jc[i]=jc[i-1]*233;39 int mx=0;num[0]=n;40 for(i=1;i<=n;i++){41 scanf("%s",s);len[i]=strlen(s);42 for(j=1;j<=len[i];j++)pre[j]=pre[j-1]*233+s[j-1];43 for(j=1;j<=len[i];j++)44 mp[j][++num[j]]=pre[len[i]]-pre[j]*jc[len[i]-j]+pre[j-1]*jc[len[i]-j];45 mp[0][i]=pre[len[i]];46 mx=max(mx,len[i]);47 for(j=1;j<=len[i];j++)b[j]=mp[j][num[j]];48 sort(b+1,b+1+len[i]);49 for(j=len[i];j;j--)if(j==len[i]||b[j+1]!=b[j])map[++cnt]=b[j];//,printf(" %lld\n",b[j]);50 // printf("! %lld\n",mp[1][num[1]]);51 }52 for(i=0;i<=mx;i++)sort(mp[i]+1,mp[i]+1+num[i]);53 sort(map+1,map+1+cnt);54 // for(i=0;i<=mx;i++){55 // for(j=1;j<=num[i];j++)printf(" %lld",mp[i][j]);puts("");56 // }57 ull tmp;58 while(m--){59 scanf("%s",s);int len=strlen(s);60 for(j=1;j<=len;j++)pre[j]=pre[j-1]*233+s[j-1];61 if((k=getl(0,pre[len]))){puts("-1");continue;}62 63 ans=get(pre[len]);//printf(" %d\n",ans);64 for(j=1;j<=len;j++){65 tmp=b[j]=pre[len]-pre[j]*jc[len-j]+pre[j-1]*jc[len-j];66 if((k=getl(j,tmp)))ans+=getr(j,tmp)-k+1;67 }68 69 sort(b+1,b+1+len);70 for(j=len;j;j--)71 if(j==len||b[j+1]!=b[j])72 if((k=getl(0,b[j])))73 ans+=getr(0,b[j])-k+1;74 75 printf("%d\n",ans);76 }77 return 0;78 }