題目：

維護一個字符串集合，支持兩種操作：

1. I x?向集合中插入一個字符串?x𝑥；
2. Q x?詢問一個字符串在集合中出現了多少次。

共有?N𝑁?個操作，所有輸入的字符串總長度不超過?10^5，字符串僅包含小寫英文字母。

輸入格式

第一行包含整數?N𝑁，表示操作數。

接下來?N𝑁?行，每行包含一個操作指令，指令為?I x?或?Q x?中的一種。

輸出格式

對于每個詢問指令?Q x，都要輸出一個整數作為結果，表示?x𝑥?在集合中出現的次數。

每個結果占一行。

數據范圍

1≤N≤2?10^4

解題分析：

本題是Acwing上的一道模板題，Trie樹又叫字典樹，就是一個像字典一樣的樹，可以幫助我們快速查找一個字符串是否出現過。通常采用樹的邊來代表字母，從根節點到樹中的某一個結點表示一個字符串，以下是一張OI Wiki的樹圖：

在圖中，aa,aba,ba,caaa,cab,cba,cc均是字符串。我們通常會在每個字符串末尾打上一個標記，用于查詢過程中判斷到這個標記時，就可讀取為一個字符串，從而達到“字典”的效果。

C++實現如下：

#include <iostream>using namespace std;const int N = 100010;int son[N][26], cnt[N], idx;
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 m;cin >> m;while(m--){char op[2];scanf("%s%s", op, str);if(*op == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}