AcWing - 835. Trie字符串统计

Solost

2023 年 03 月 28 日

217 次浏览

暂无评论

1377字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F28%2Fimage.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/837/)

## 题解

```cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int idx;
int tr[N][30];
int cnt[N];
void insert(string s){
    int p = 0;
    for(auto u : s){
        u -= 'a';
        if(!tr[p][u]) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    cnt[p]++;//不同题目cnt计数的位置不同，因为这道题统计的是以这个串为结尾的个数，所以全部加完才会计数
}

int query(string s){
    int p = 0;
    for(auto u : s){
        u -= 'a';
        if(!tr[p][u]) return 0;//如果此时还没有遍历完匹配串树里面就已经没有相关节点了，那么就不存在
        p = tr[p][u];
    }
    return cnt[p];
}

void solve(){
    int n;
    cin >> n;
    while(n--){
        char op;
        string s;
        cin >> op >> s;
        if(op == 'I') insert(s);
        else cout << query(s) << endl;
    }
}
int main(){
    // IOS;
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 28 日