ACWING 835. Trie字符串统计
#include <bits/stdc++.h> using namespace std; const int N = 100005; int idx; //每个节点的唯一标识 int son[N][26], cnt[N]; char s1[N], s2[N]; void insert(char s[]) { int p = 0; for (int i = 0; s[i]; ++i) { int u = s[i] - 'a'; if (!son[p][u]) { //创建新节点 son[p][u] = ++idx; } p = son[p][u]; } ++cnt[p]; //son[p][*]一定为0, 代表单词结尾 } int query(char s[]) { int p = 0; for (int i = 0; s[i]; ++i) { int u = s[i] - 'a'; if (son[p][u] == 0) { //无法找到下一个字符,代表该字符串没有出现过 return 0; } p = son[p][u]; } return cnt[p]; } int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif int n; cin >> n; while (n--) { scanf("%s %s", &s1, &s2); if (s1[0] == 'I') { insert(s2); } else { cout << query(s2) << endl; } } fclose(stdin); fclose(stdout); return 0; }