題目

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

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

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

輸入格式

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

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

輸出格式

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

每個結果占一行。

數據范圍

KaTeX parse error: Undefined control sequence: \* at position 14: 1 \le N \le 2\?*?10^4

輸入樣例：

5
I abc
Q abc
Q ab
I ab
Q ab

輸出樣例：

1
0
1

解題思路

這個題需要我們創建一個trie樹來解決問題。

假設我們需要插入的兩個字符串是 abc 和 abdef，此時樹就長這個樣子。

假設再插入一個 abdf，那么就變成這個樣子

本題還需要能夠查詢 一個字符串中出現的次數

所以在每次插入一個字符串時，都需要在末尾的字母處標記，具體怎么操作的還需要結合一下代碼

代碼

首先準備階段如下：

其中 數組 son每一行代表 一個節點，每一行當中的列代表著 他是 a b c … z 中的哪一種字母，它存儲的值，是他的兒子，也就是它的下一個節點的位置，如果值是0的話則代表它沒有兒子。

idx代表著現在數組 son 用到那個點了。

數組cnt 用來標記每一個字符串出現了多少次。

數組str 用來臨時存儲要插入的字符串。

---

插入函數：

參數為一個字符串，寫成數組和 指針的形式都可以。

這個p的含義是 數組son 的行數，也就是表示節點的位置。

p = 0代表當前 為 根節點。

接下來遍歷整個字符串，拿到字符串的每一個字母所對應的每一行的列坐標（比如 a對應 0下標，b對應 1下標）

這句話的意思是，如果此時沒有該處沒有被插入值也就是為0時，那么此時就創建一條路，給他個兒子節點，這個兒子的位置由 idx 決定，Idx的一生會從 1 開始 加加，作為每次插入點的坐標。

接著 p 更新到它兒子節點的位置。

最后在 數組cnt p位置上 自增1。

至此插入操作就完成了。

---

接著寫查詢函數。

同樣，與插入的前面部分相同，u 是字符串中字母所對應的下標

與前面不同的點是，插入操作是 沒路創造路，而查詢操作是 沒路則代表他這個字符串就不存在，所以就出現了0次，所以返回0.

接著還是 指到下一個節點

最后遍歷完之后，如果沒有被 return 0，那么此時 cnt[ p ] 的值就是 該字符串出現的 次數。

---

接著是main函數部分

main函數我們只需要根據題目當中的輸入和輸出，然后調用對應的方法即可。

完整代碼：

#include <iostream>
using namespace std;const int N = 1e5+10;int son[N][26], idx, cnt[N];
char str[N];int n;void insert(char* str)
{int p = 0;for (int i = 0; str[i] != 0; i++){int u = str[i] - 'a';if(son[p][u] == 0) 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] == 0) return 0;p = son[p][u];}return cnt[p];
}int main()
{scanf("%d", &n);while (n -- ){char op[2];scanf("%s", op);scanf("%s", str);if (op[0] == 'I')   insert(str);   else printf("%d\n", query(str));}return 0;
}

---

完