题目链接
字典树模板题
测试模板
此题这里允许单词重复,(读错题WA好多
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
const int N = 1e5 + 5;
struct Trie
{
int next[N*30][26], sz[N*30*26], ed[N*30*26], pos, root;
int newnode()
{
for(int i = 0; i < 26; i++)
next[pos][i] = -1;
sz[pos] = 0;
ed[pos] = 0;
return pos++;
}
void init()
{
pos = 0;
root = newnode();
}
void insert(string s)
{
int n = s.size();
int now = root;
sz[now]++;
for(int i = 0; i < n; i++)
{
int b = s[i]-'a';
if(next[now][b] == -1) next[now][b] = newnode();
now = next[now][b];
sz[now]++;
}
/*if(ed[now] == 0)
ed[now] = 1;
else
{
int now = root;
sz[now]--;
for(int i = 0; i < n; i++)
{
int b = s[i]-'a';
now = next[now][b];
sz[now]--;
}
}*/
}
int query(string s)
{
int n = s.size();
int now = root;
for(int i = 0; i < n; i++)
{
int b = s[i]-'a';
if(next[now][b] == -1) return 0;
now = next[now][b];
}
return sz[now];
}
};
Trie t;
int n,m;
string tmp;
int main()
{
t.init();
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
cin>>tmp;
t.insert(tmp);
}
scanf("%d", &m);
for(int i = 0; i < m; i++)
{
cin>>tmp;
printf("%d
", t.query(tmp));
}
return 0;
}