首页 > 代码库 > trie
trie
POJ 3630
给出n个字符串,问是否存在一个字符串是另一个的前缀。
# include <cstring># include <cstdio>const int maxlen = 15;const int maxw = 10;const int maxn = 10005 * maxw;char str[maxlen];int n;int root, id;int next[maxn][maxw];bool lc[maxn];bool check_add(int e, int ch){ if (next[e][ch]) return true; next[e][ch] = ++id; lc[id] = false; memset(next[id], 0, sizeof(next[id])); return false;}void solve(void){ bool ans = true; scanf("%d", &n); id = 0; root = 0; lc[root] = false; memset(next[root], 0, sizeof(next[root])); for (int i = 0; i < n; ++i) { scanf("%s", str); if (!ans) continue; int e = root; bool local = false; for (int j = 0; str[j]; ++j) { if ( !check_add(e, str[j]-‘0‘) ) local = true; e = next[e][ str[j]-‘0‘ ]; if (lc[e]) ans = false; } lc[e] = true; if (!local) ans = false; } printf(ans ? "YES\n":"NO\n");}int main(){ int T; scanf("%d", &T); for (int i = 0; i < T; ++i) { solve(); } return 0;}
Uva 11488 Hyper Prefix Sets
给出n个01串,问其所有子集中所有串的公共前缀和串的数目积的最大值。
// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2483# include <cstring># include <cstdio># include <algorithm>const int maxw = 2;const int maxlen = 205;const int maxn = 50000 * maxw;int n;int root, id;int cnt[maxn];int next[maxn][maxw];bool check_add(int e, int ch) { if (next[e][ch]) return true; next[e][ch] = ++id; cnt[id] = 0; memset(next[id], 0, sizeof(next[id])); return false;}char str[maxlen];void solve(){ int ans = 0; scanf("%d", &n); root = 0; id = 0; cnt[root] = 0; memset(next[root], 0, sizeof(next[root])); for (int i = 0; i < n; ++i) { scanf("%s", str); int e = root; for (int j = 0; str[j]; ++j) { check_add(e, str[j]-‘0‘); e = next[e][ str[j]-‘0‘ ]; ++cnt[e]; ans = std::max(ans, cnt[e]*(j+1)); } } printf("%d\n", ans);}int main(){ int T; scanf("%d", &T); for (int ica = 0; ica < T; ++ica) { solve(); } return 0;}
leetcode Longest Common Prefix
没在OJ上找到LCP的题,只有leetcode上有(此处省略吐槽1000字)。
这道题是求所有串的LCP,所以裸的字典树足够,代码:
// https://oj.leetcode.com/problems/longest-common-prefix/# include <vector># include <string># include <cstring># include <algorithm># include <iostream># define maxnode 1005using namespace std;class Solution {public: int root, id; int next[maxnode][256]; int cnt[maxnode]; bool check_add(int e, int ch) { if (next[e][ch]) return true; next[e][ch] = ++id; memset(next[id], 0, sizeof(next[id])); return false; } string longestCommonPrefix(vector<string> &strs) { int n = strs.size(); if (n <= 0) return string(""); id = 0; root = 0; memset(next[root], 0, sizeof(next[root])); cnt[root] = 0; int ans = 0; for (int i = 0; i < n; ++i) { int e = root; for (int j = 0; strs[i][j]; ++j) { check_add(e, strs[i][j]); e = next[e][ strs[i][j] ]; ++cnt[e]; if (cnt[e] >= n) ans = std::max(ans, j+1); } } return string(strs[0].substr(0, ans)); }};
trie
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。