Trie字符串统计(计算字符串在集合中出现次数)(01trie)

01trie我们可以把一个字符串放在一个树上
tr[N][27] 其中N表示父亲节点,[27]表其映射的子节点,例子建树如下

之后知道这样建树之后就比较好理解了

#include
#define ll long long
using namespace std;
const int maxn = 2e4 + 100;
const int N = 1e5 + 5;
int tr[maxn][30];
char str[N];
int idx,cnt[maxn],n;
void insert(char s[], int len){
	int p = 0;
	for(int i = 0; i < len; i++){
		int now = s[i] - 'a' + 1;
		if(!tr[p][now]){
			tr[p][now] = ++ idx;
		}
		p = tr[p][now];
	}
	cnt[p]++;
}
int query(char s[], int len){
	int p = 0;
	for(int i = 0; i < len; i++){
		int now = s[i] - 'a' + 1;
		if(!tr[p][now])return 0;
		p = tr[p][now];
	}
	return cnt[p];
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		char op;
		cin >> op >> str;
		int len = strlen(str);
		if(op == 'I'){
			insert(str, len);
		}else{
			cout << query(str, len) << endl;
		}
	}
}