字符串—— 前缀统计（trie树）
trie树：一种用于实现字符串快速检索的多叉树结构。形如下图
传送门：
要点：这里要累加路径上的cnt【p】的值
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N],idx;
char a[1000000];
int n,m;
void insert(char a[])
{
int p=0;
for(int i=0;a[i];i++)
{
int u=a[i]-a;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
int query(char a[])
{
int p=0,sum=0;
for(int i=0;a[i];i++)
{
int u=a[i]-a;
p=son[p][u];
if(!p) return sum;
sum+=cnt[p];
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%s",a);
insert(a);
}
for(int i=1;i<=m;i++)
{
scanf("%s",a);
cout<<query(a)<<endl;
}
return 0;
}
