Trie string statistics

Maintain a collection of strings , Two operations are supported ：

1. I x  Insert a string into the collection  x;
2. Q x  Ask how many times a string appears in the collection .

share NN Operations , The total length of the input string does not exceed 1e5, 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 xx Number of occurrences in the set .

Each result takes up one line .

Data range

1≤N≤2∗1e4

sample input ：

5
I abc
Q abc
Q ab
I ab
Q ab

sample output ：

1
0
1

 Code:

#include <iostream>
#include <stdio.h>

using namespace std;

typedef int Status;

const int N = 100010;

int n, idx, cnt[N], son[N][26];
char str[N], op[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] ++; // Count 
}

Status query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u])  return 0; // Stop without this string 
        p = son[p][u];
    }
    return cnt[p];
}

signed main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> op >> str;
        if(op[0] == 'I')  insert(str);
        else  printf("%d\n", query(str));
    }
}