Trie 树 算法实现 C++

一、题目描述

维护一个字符串集合，支持两种操作：

• I x：向集合中插入一个字符串x
• Q x：询问字符串x在集合中出现了多少次

共有N个操作，所有输入字符串的总长度不超过10^5，字符串仅包含小写英文字母。

输入格式

第一行包含整数N，表示操作数。

接下来N行，每行包含一个操作：

I x

或者：

Q x

输出格式

对于每个查询操作Q x，输出字符串x在集合中出现的次数。

每个结果占一行。

数据范围

1 ≤ N ≤ 2 × 10^4

输入样例

5 I abc Q abc Q ab I ab Q ab

输出样例

1 0 1

算法实现：

#include<iostream> using namespace std; const int N =100010; int son[N][26], idx, cnt[N]; char str[N]; void insert(char str[]) { int p=0; for(int i=0; str[i]; i++) { int u = str[i]-'a'; if(!son[p][u]) son[p][u]=++idx; p=son[p][u]; } cnt[p]++; } int query(char str[]) { int p=0; for(int i=0; str[i]; i++) { int u = str[i]-'a'; if(!son[p][u]) return 0; p=son[p][u]; } return cnt[p]; } int main() { int n; cin>>n; while(n--) { char op[2]; cin>>op>>str; if(op[0]=='I') insert(str); if(op[0]=='Q') cout<<query(str)<<endl; } return 0; }