搜索
您的当前位置:首页正文

【刷题】数据结构——Trie树【模板】

来源:独旅网

不妨设有字符串ab、abc、abd、ba,那么将建立如下的字典树。

#include <iostream>
using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx; // 26个字母,cnt存编号i下标的个数,下标0为空。
int n;
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;
		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;
		p = son[p][u];
	}
	return cnt[p];
}

int main() {
	scanf("%d", &n);
	while(n -- ) {
		char op[2]; // op[1]用于吞掉空格 
		scanf("%s%s", op, str);
		if (op[0] == 'I') insert(str);
		else printf("%d\n", query(str));
	}
	return 0;
}

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top