維護一個字元串集合,支援兩種操作:
I x 向集合中插入一個字元串 x;
Q x 詢問一個字元串在集合中出現了多少次。
共有 N個操作,輸入的字元串總長度不超過 10^5,字元串僅包含小寫英文字母。
輸入格式
第一行包含整數 N,表示操作數。
接下來 N行,每行包含一個操作指令,指令為 I x 或 Q x 中的一種。
輸出格式
對于每個詢問指令 Q x,都要輸出一個整數作為結果,表示 x在集合中出現的次數。
每個結果占一行。
資料範圍
1≤N≤2∗10^4
輸入樣例:
5
I abc
Q abc
Q ab
I ab
輸出樣例:
1
算法一:用标準庫,利用标準庫裡面的集合即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <unordered_set>
using namespace std;
unordered_multiset <string> se;
int main()
{
int t;
cin >> t;
while(t --)
{
char ch;
string s;
cin >> ch >> s;
if(ch == 'I') se.insert(s);
else printf("%d\n", se.count(s));
}
return 0;
}
算法二:trie樹
#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[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;//作為tire樹的路徑
p = son[p][u];
}
cnt[p] ++ ;//在結尾處标記出現了幾次
}
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;//tire樹沒有路徑了
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
scanf("%s%s", op, str);
if (*op == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}