当前位置:网站首页>Trie string statistics

Trie string statistics

2022-06-28 06:26:00 MITBlick

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));
    }
}

原网站

版权声明
本文为[MITBlick]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202161426299210.html