维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 x
- ;
Q x
询问一个字符串在集合中出现了多少次。
共有 N
个操作,输入的字符串总长度不超过 105,字符串仅包含小写英文字母。
输入格式
第一行包含整数 N
,表示操作数。
接下来 N
行,每行包含一个操作指令,指令为 I x
或 Q x
中的一种。
输出格式
对于每个询问指令 Q x
,都要输出一个整数作为结果,表示 x
在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗104
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; // trie要事先确定好可能出现的单词总长度 int trie[N][26], idx, cnt[N]; // trie存树,idx记录当前树延伸到的位置,cnt记录答案 void tire_insert(char c[]) // 向树中插入单词 { int p = 0;// 记录当前位于树的哪里 for(int i = 0; c[i]; i ++ ) { int t = c[i] - 'a';// 将字母转化成数字 if(!trie[p][t]) trie[p][t] = ++ idx;// 由于0代表根或者不存在,故新节点从1开始 p = trie[p][t];// 继续记录 } cnt[p] ++ ; } int trie_query(char c[])// 查找单词格式 { int p = 0; for(int i = 0; c[i]; i ++ ) { int t = c[i] - 'a'; if(!trie[p][t]) return 0;// 与插入不同,当单词中间断开时,证明这个单词不存在 p = trie[p][t]; } return cnt[p];// 返回单词个数 } int main() { int t; char s[3], sx[N]; scanf("%d", &t); while(t -- ) { scanf("%s%s", s, sx); if(s[0] == 'I') tire_insert(sx); else printf("%d\n", trie_query(sx)); } return 0; }
标签:cnt,tire,int,++,单词,trie,字典 From: https://www.cnblogs.com/leyuo/p/16609976.html