#include <iostream>
#include <string.h>
using namespace std;
const int NUM = 5e4 + 1;
// 用数组定义字典树，存储下一个字符的位置
int trie[NUM][26];
// 以某一字符串为前缀的单词的数量
int num[NUM] = { 0 };
// 当前新分配的存储位置
int pos = 1;
// 在字典数中插入某个单词
void trieInsert(string str)
{
int p = 0;
for (int i = 0; str[i]; i++) {
int n = str[i] - 'a';
if (trie[p][n] == 0) {
// 如果对应字符没有值，存储下一个索引的值
trie[p][n] == pos++;
}
p = trie[p][n];
num[p]++;
}
}
// 返回以某个字符串为前缀的单词的数量
int trieFind(string str)
{
int p = 0;
for (int i = 0; str[i]; i++) {
int n = str[i] - 'a';
if (trie[p][n] == 0) {
return 0;
}
p = trie[p][n];
}
return num[p];
}