字典树p8036
Description
给定 �n 个模式串 �1,�2,…,��s1,s2,…,sn 和 �q 次询问，每次询问给定一个文本串 ��ti，请回答 �1∼��s1∼sn 中有多少个字符串 ��sj 满足 ��ti 是 ��sj 的前缀。
一个字符串 �t 是 �s 的前缀当且仅当从 �s 的末尾删去若干个（可以为 0 个）连续的字符后与 �t 相同。
输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。
Input
本题单测试点内有多组测试数据。
输入的第一行是一个整数，表示数据组数 �T。
对于每组数据，格式如下：
第一行是两个整数，分别表示模式串的个数 �n 和询问的个数 �q。
接下来 �n 行，每行一个字符串，表示一个模式串。
接下来 �q 行，每行一个字符串，表示一次询问。
Output
按照输入的顺序依次输出各测试数据的答案。
对于每次询问，输出一行一个整数表示答案。
Sample 1
| Inputcopy | Outputcopy |
|---|---|
3 3 3 fusufusu fusu anguei fusu anguei kkksc 5 2 fusu Fusu AFakeFusu afakefusu fusuisnotfake Fusu fusu 1 1 998244353 9 |
2 1 0 1 2 1 |
Hint
数据规模与约定
对于全部的测试点，保证 1≤�,�,�≤1051≤T,n,q≤105，且输入字符串的总长度不超过 3×1063×106。输入的字符串只含大小写字母和数字，且不含空串。
说明
std 的 IO 使用的是关闭同步后的 cin/cout，本题不卡常。
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int tr[N][100];
int idx=0;
int cnt[N];
int change(char x){
if(x<='z'&&x>='a')return x-'a';
else if(x<='Z'&&x>='A')return x-'A'+26;
else return x-'0'+52;
}
void insert(string b){
int u=0;
for(int i=0;i<b.size();i++){
int j=change(b[i]);
if(!tr[u][j]){
idx++;
tr[u][j]=idx;
}
u=tr[u][j];
cnt[u]++;
}
}
int search(string b){
int u=0;
for(int i=0;b[i];i++){//b[i] == i<b.size()
int j=change(b[i]);
if(!tr[u][j]){
return 0;
}
u=tr[u][j];
}
return cnt[u];
}
void sol(){
for(int i=0;i<=idx;i++){
memset(tr[i],0,sizeof(tr[i]));
cnt[i]=0;
}
idx=0;
int n,q;cin>>n>>q;
string a;
while(n--){
cin>>a;
insert(a);
}
while(q--){
cin>>a;
cout<<search(a)<<endl;
}
}
int main(){
int t;cin>>t;
while(t--)sol();
return 0;
}
