题目大意
给定 \(n\) 个字符串，长度总和为 \(m\)，进行 \(q\) 次询问，每次询问给定两个字符串 \(p,s\)，问所有的字符串中以 \(p\) 为前缀且以 \(s\) 为后缀的有多少个。
思路分析
分享一个船新的答辩做法。（目前是最劣解）
考虑哈希，对每个给定的字符串前后各做一遍哈希，将所有的哈希值离散化，对每个字符串往其对应的所有哈希值的 vector 中存入自己的编号。
那么我们的问题就变成了：
- 给定 \(m\) 个集合，集合中数的总和在 \(O(m)\) 数量级，进行 \(q\) 次询问，每次询问两个集合的交集的元素个数。
这个问题可以通过 bitset 解决。
简单的说，我们可以对每个哈希值建一个 bitset，每次求交集的时候只需要与一下对应的 bitset 再求一下元素个数就可以了，单次时间复杂度为 \(O(\frac{nm}{w})\)，可以接受。
但空间复杂度无法接受，因此我们考虑根号分治平衡时空复杂度。
具体的说，我们设定一个阈值 \(B\)，只对所有元素个数大于 \(B\) 的哈希值建立 bitset。查询时，对元素个数小于 \(B\) 的集合直接暴力扫描加入一个公用的 bitset，再与另一个 bitset 与一下，最后将公用的 bitset 清空。
这样我们的时间复杂度就为：\(O(qB+\frac{nq}{w}+m\log m)\)，空间复杂度为 \(O(\frac{nm}{vB})\)，其中 \(w=64,v=8\)，时空都还可以接受。
于是你满怀希望的交了一发，取得了 \(35\text{pts}\) 的好成绩，最大点跑了 \(6s\)。
开始大力卡常：
-
将哈希值离散化的
map换成排序加去重加lower_bound，时间降为 \(4.5s\)。 -
将
unsigned long long自然溢出哈希改为unsigned int自然溢出哈希，时间降为 \(4s\)。 -
加字符串快读快写，时间降为 \(3.5s\)。
-
将固定阈值 \(B=1000\) 改为 \(B=\sqrt {q}\)，时间降为 \(3s\)。
-
在查询时先判断哈希值存不存在，时间降为 \(2s\)。
-
将前哈希和后哈希分开，各自独立离散化，时间降为 \(1.5s\)。
这样，我们就以
的好成绩喜提最劣解通过本题。
代码
（最劣解的代码也要看？）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
using namespace std;
const int M=5010,L=100010,N=2000100,P=133,Q=133;
typedef unsigned int ull;
int n,m,tt,tt2,cnt,tot1,tot2,BL,sum;
int vis1[N<<1],vis2[N<<1];
ull v3[N],v4[N],vHash1[N],vHash2[N];
int vid1[N],vid2[N];
vector<int> v1[N<<1],v2[N<<1];
bitset<L> bset[M];
char s[N],s1[N],s2[N];
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<16,stdin),S==T)?EOF:*S++)
char B[1<<16],*S=B,*T=B;
inline void readint(int &x){
x=0;char ch=getchar();
while(ch<'0'||'9'<ch) ch=getchar();
while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline int readchar(char a[]){
int len=0;
char ch=getchar();
while(ch<'A'&&'Z'<ch) ch=getchar();
while('A'<=ch&&ch<='Z') a[++len]=ch,ch=getchar();
return len;
}
void write(int x){
int k=x/10;
if(k) write(k);
putchar(x%10+'0');
}
int main(){
readint(n);readint(m);
for(int i=1;i<=n;i++){
int len=readchar(s);
sum+=len;
ull Hash=1;
for(int j=1;j<=len;j++){
Hash=Hash*P+s[j]+Q;
v3[++tt]=Hash;tot1++;
vHash1[tot1]=Hash;vid1[tot1]=i;
}
Hash=1;
for(int j=len;j>=1;j--){
Hash=Hash*P+s[j]+Q;
v4[++tt2]=Hash;tot2++;
vHash2[tot2]=Hash;vid2[tot2]=i;
}
}
BL=pow(m,0.5);
sort(v3+1,v3+tt+1);sort(v4+1,v4+tt2+1);
tt=unique(v3+1,v3+tt+1)-v3-1;
tt2=unique(v4+1,v4+tt2+1)-v4-1;
for(int i=1;i<=tot1;i++)
v1[lower_bound(v3+1,v3+tt+1,vHash1[i])-v3].push_back(vid1[i]);
for(int i=1;i<=tot2;i++)
v2[lower_bound(v4+1,v4+tt2+1,vHash2[i])-v4].push_back(vid2[i]);
for(int i=1;i<=tt;i++)
if(v1[i].size()>BL){
vis1[i]=++cnt;
for(int j=0;j<v1[i].size();j++) bset[cnt][v1[i][j]]=1;
}
for(int i=1;i<=tt2;i++)
if(v2[i].size()>BL){
vis2[i]=++cnt;
for(int j=0;j<v2[i].size();j++) bset[cnt][v2[i][j]]=1;
}
while(m--){
int len1=readchar(s1);
int len2=readchar(s2);
ull Hash1=1,Hash2=1;
for(int i=1;i<=len1;i++)
Hash1=Hash1*P+s1[i]+Q;
for(int i=len2;i>=1;i--)
Hash2=Hash2*P+s2[i]+Q;
int x=lower_bound(v3+1,v3+tt+1,Hash1)-v3;
int y=lower_bound(v4+1,v4+tt2+1,Hash2)-v4;
if(v3[x]!=Hash1||v4[y]!=Hash2){cout<<"0\n";continue;}
if(v1[x].size()>BL&&v2[y].size()>BL){
write((bset[vis1[x]]&bset[vis2[y]]).count());putchar('\n');
}
else if(v1[x].size()>BL||v2[y].size()>BL){
if(v1[x].size()>BL){
bitset<L> st;
for(auto it:v2[y]) st[it]=1;
write((st&bset[vis1[x]]).count());putchar('\n');
}
else{
bitset<L> st;
for(auto it:v1[x]) st[it]=1;
write((st&bset[vis2[y]]).count());putchar('\n');
}
}
else{
bitset<L> st,st2;
for(auto it:v1[x]) st[it]=1;
for(auto it:v2[y]) st2[it]=1;
write((st&st2).count());putchar('\n');
}
}
return 0;
}