首页 > 代码库 > 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