题意：
给了一个母串S, 每次循环给了一个模板串，问模板串在母 串中“匹配”了多少次？“匹配”的意思就是首字母和尾字母一样， 中间字母顺序可以换。
题解：
字符串hash.我们将询问字符串的首尾特殊hash，然后将询问串的长度存入到vector里面。
然后遍历一遍原串，将所有是询问串长度的子串的哈希值插入到vecor并排序，然后对于该询问，我们只要用lower_bound和upper_bound查找有多少哈希值等于我的就行了，记录答案，最后输出答案。
参考代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define pb push_back #define base 1000039 #define pii pair<int,int> #define pil pair<int,ll> #define mkp make_pair #define RI register int const int INF=0x3f3f3f3f; const int maxn=1e5+10; const int maxm=2e4+10; int T,Q,ans[maxm]; char s1[maxn<<1],s2[maxn]; ull p[30],x[maxm],y[maxn]; vector<int> vec[maxn]; inline int idx(char ch){return ch-'a'+1;} inline void preHash() { p[0]=1; for(RI i=1;i<30;++i) p[i]=p[i-1]*base; } inline void work() { for(RI i=1;i<=Q;++i) { scanf("%s",s2+1); int len=strlen(s2+1); x[i]=idx(s2[1])*p[28]+idx(s2[len])*p[29]; for(RI j=2;j<=len-1;++j) x[i]+=p[idx(s2[j])]; vec[len].pb(i); } } inline void solve() { int len=strlen(s1+1); for(RI i=1;i<=len;++i) { int siz=vec[i].size(); if(!siz) continue; ull pre=0; int cnt=0; for(RI j=1;j<i;++j) pre=pre+p[idx(s1[j])]; for(RI j=i;j<=len;++j) { pre=pre+p[idx(s1[j])]; if(j!=i) pre-=p[idx(s1[j-i])]; ull res=pre-p[idx(s1[j])]-p[idx(s1[j-i+1])]+(idx(s1[j-i+1]))*p[28]+(idx(s1[j]))*p[29]; y[++cnt]=res; } sort(y+1,y+1+cnt); for(RI j=0,siz=vec[i].size();j<siz;++j) { int dn=lower_bound(y+1,y+1+cnt,x[vec[i][j]])-y; int up=upper_bound(y+1,y+1+cnt,x[vec[i][j]])-y; ans[vec[i][j]]=up-dn; } } } int main() { preHash(); scanf("%d",&T); while(T--) { for(RI i=0;i<maxn;++i) vec[i].clear(); scanf("%s%d",s1+1,&Q); work(); solve(); for(RI i=1;i<=Q;++i) printf("%d\n",ans[i]); } return 0; }