Trie 树 算法实现 C++

一、题目描述维护一个字符串集合支持两种操作I x向集合中插入一个字符串xQ 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算法实现#includeiostream using namespace std; const int N 100010; int son[N][26], idx, cnt[N]; char str[N]; void insert(char str[]) { int p0; for(int i0; str[i]; i) { int u str[i]-a; if(!son[p][u]) son[p][u]idx; pson[p][u]; } cnt[p]; } int query(char str[]) { int p0; for(int i0; str[i]; i) { int u str[i]-a; if(!son[p][u]) return 0; pson[p][u]; } return cnt[p]; } int main() { int n; cinn; while(n--) { char op[2]; cinopstr; if(op[0]I) insert(str); if(op[0]Q) coutquery(str)endl; } return 0; }