acwing 835. Trie string statistics

Trie Trees ： Efficiently store and find the data structure of string collection .

It's usually used trie , The title limits the type of characters 26 A or 52 individual .

If you want to trie Save the following set of strings in , The principle is as follows ：

abcdef、abdef、aced、bcdf、bcff、cdaa、bcdc

Storage ：

Generally speaking , Mark all the ending words , Otherwise, you can't find the word where it may be repeated .

lookup ：
Go straight down one layer at a time , If there is trie A character that ends with a search string in the tree , be true, conversely ,false.

subject ：

Maintain a collection of strings , Two operations are supported ：

I x Insert a string into the collection x;
Q x Ask how many times a string appears in the collection .
share N Operations , The total length of the input string does not exceed 105, The string contains only lowercase letters .

Input format
The first line contains integers N, Represent operands .

Next N That's ok , Each line contains an operation instruction , Instructions for I x or Q x One of the .

Output format
For each inquiry instruction Q x, You have to output an integer as the result , Express x Number of occurrences in the set .

Each result takes up one line .

Data range
1≤N≤2∗104
sample input ：
5
I abc
Q abc
Q ab
I ab
Q ab
sample output ：
1
0
1

Ideas ：

1. trie Construction
2. Each node is uniquely identified
3. Each string has a flag at the end , Save the quantity

code:

#include <iostream>

using namespace std;

const int N = 100010;

// son[N][26] : N  Express N layer 
//  Maximum per node 26, cnt Express   By the end of N The number of strings at the end of nodes ,idx Index representation 
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])
{
    
    int p = 0;
    for(int i=0; str[i]; i++)   // char str[] With '\0'  ending , You can do this 
    {
    
        int u = str[i] - 'a';  //  Mapping to 0 -25
        if(!son[p][u]) son[p][u] = ++idx;  //  If it doesn't exist , created , Each node has a unique number 
        p = son[p][u];
    }
    cnt[p] ++;   //  The number ending at this point  + 1 
}

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];
        cin >> op >> str;
        if(op[0] == 'I')  insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}