Acwing835. Trie字元串統計（Tire模闆）

就是一個Tire模闆

維護一個字元串集合，支援兩種操作：

“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

1

代碼

#include <iostream>
using namespace std;
const int N=100010;
int  son[N][26];
char str[N];
int idx;int cnt[N];
void insert(){
    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(){
    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 t;
    cin >> t;
    while(t--){
        char c;
        cin >> c;
        cin >> str;
        if(c=='I'){
            insert();
        }else{
            cout << query() << "\n";
        }
        
    }
}