https://nanti.jisuanke.com/t/41415
题意：两个字符串匹配的条件是：第一个和最后一个相同中间的种数和数量相同。q次查询匹配个数。
hash匹配，由于卡空间，我们离线处理，枚举查询串的长度（不超过sqrt(q）)，二分得到匹配个数。
1 #define bug(x) cout<<#x<<" is "<<x<<endl
2 #define IO std::ios::sync_with_stdio(0)
3 #define ull unsigned long long
4 #include <bits/stdc++.h>
5 #define iter ::iterator
6 #define pa pair<int,ull>
7 using namespace std;
8 #define ll long long
9 #define mk make_pair
10 #define pb push_back
11 #define se second
12 #define fi first
13 #define ls o<<1
14 #define rs o<<1|1
15 const int N=1e5+5;
16 int T;
17 int n,m;
18 ll mod[3]={1000000007,998244353};
19 ll base[3]={127,131};
20 int a[N];
21 vector<pa>P[N];
22 int ans[N];
23 ull z[N];
24 ull p[405];
25 ll cal(int id){
26 char s[N];
27 scanf("%s",s);
28 int L=strlen(s);
29 a[id]=L;
30 ull res=0;
31 for(int i=1;i<L-1;i++){
32 res+=p[s[i]-'a'];
33 }
34 res+=(s[0]-'a'+1)*p[233];
35 res+=(s[L-1]-'a'+1)*p[234];
36 return res;
37 }
38 int c[N];
39 char S[N];
40 int main(){
41 p[0]=1;
42 for(int i=1;i<=400;i++){
43 p[i]=p[i-1]*mod[0];
44 }
45 scanf("%d",&T);
46 while(T--){
47 scanf("%s",S);
48 scanf("%d",&n);
49 for(int i=1;i<=n;i++){
50 ull res=cal(i);
51 pa p=mk(i,res);
52 P[a[i]].pb(p);
53 }
54 sort(a+1,a+1+n);
55 int na=unique(a+1,a+1+n)-a-1;
56 int ns=strlen(S);
57 for(int i=0;i<ns;i++){
58 c[i]=S[i]-'a';
59 }
60 for(int i=1;i<=na;i++){
61 int cnt=0;
62 int k=a[i];
63 ull h=0;
64 for(int j=0;j<ns;j++){
65 if(j>=k-1){
66 h-=p[c[j-k+1]];
67 ull res=h+p[233]*(c[j-k+1]+1)+p[234]*(c[j]+1);
68 z[++cnt]=res;
69 }
70 h+=p[c[j]];
71 }
72 sort(z+1,z+1+cnt);
73 for(auto tmp:P[k]){
74 int x=tmp.fi;
75 ull y=tmp.se;
76 int l=lower_bound(z+1,z+1+cnt,y)-z;
77 int r=upper_bound(z+1,z+1+cnt,y)-z;
78 ans[x]=r-l;
79 }
80 P[k].clear();
81 }
82 for(int i=1;i<=n;i++){
83 printf("%d\n",ans[i]);
84 }
85 }
86 }