trie

大雪料理の授業(メモ)
データ構造(二)
1.trie
(1).テンプレート()

int son[N][26], cnt[N], idx;
// 0       ，     
// son[][]            
// cnt[]              

//        
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];
}

AcWing 835.Trie文字列統計
文字列のセットを維持し、2つの操作をサポートします.
「I x」はセットに文字列xを挿入します.「Q x」は文字列が集合中に何回現れたかを問い合わせる.N個の操作があり、入力された文字列の総長さは105を超えず、文字列は小文字英字のみを含む.
入力フォーマットの最初の行は整数Nを含み、操作数を表します.
次のN行は、各行に対して、「I x」または「Q x」のいずれかの動作命令を含む.
出力フォーマットは、各照会コマンド「Q x」に対して、結果として1つの整数を出力し、xがセットに出現する回数を表します.
各結果が1行を占める.
データ範囲1≦N≦2∗104入力サンプル例:5 I abc Q ab I ab Q ab出力サンプル例:1

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