首页 > 其他 > 详细

Tire

时间:2020-10-31 16:28:38      阅读:41      评论:0      收藏:0      [点我收藏+]

Trie

const int MAXN = 1e5 + 5;

int trie[MAXN][26], cnt[MAXN], tot = 1, n, m;
bool end[MAXN];
char str[MAXN];

void insert(char* str) {
	int len = strlen(str), p = 1;
	for (int k = 0; k < len; k++) {
		int ch = str[k] - ‘a‘;
		if (trie[p][ch] == 0) trie[p][ch] = ++tot;
		p = trie[p][ch];
	}
	end[p] = 1;
}
int search(char* str) {
	int len = strlen(str), p = 1, sum = 0;
	for (int k = 0; k < len; k++) {
		p = trie[p][str[k] - ‘a‘];
		if (p == 0) return false;
	}
	return end[p];
}

0-1Trie

void insert(int x) {
	int p = 1;
	for (int i = 30; i >= 0; i--) {
		int u = (x >> i) & 1;
		if (trie[p][u] == 0) trie[p][u] = ++tot;
		p = trie[p][u];
	}
	end[p] = 1;
}

int search(int x) {
	int p = 1, sum = 0;
	for (int i = 30; i >= 0; i--) {
		int u = (x >> i) & 1;
		if (trie[p][u ^ 1]) {
			p = trie[p][u ^ 1];
			sum += (1 << i);
		} else p = trie[p][u];
	}
	return sum;
}

Tire

原文:https://www.cnblogs.com/cqbz-ChenJiage/p/casd.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!