AcWing 142. 前缀统计
原题链接
简单
作者:
RanPg
,
2023-01-08 22:16:52
,
所有人可见
,
阅读 144
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 26 * N;
int son[M][26], idx, cnt[N];
void insert(string str) // 建立trie树
{
int p = 0;
for(int i = 0; i < str.size(); i ++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++; //标记最后一个字符即标记前缀
}
int query(string str) //查询有多少个前缀
{
int p = 0, ans = 0; //ans统计前缀
for(int i = 0; i < str.size(); i ++)
{
int u = str[i] - 'a';
if(!son[p][u]) break; // 查无此串跳出循环
p = son[p][u];
ans += cnt[p];
}
return ans;
}
int main()
{
int n, m;
cin >> n >> m;
while(n --)
{
string str1;
cin >> str1;
insert(str1);
}
while(m --)
{
string str2;
cin >> str2;
cout << query(str2) << endl;
}
return 0;
}