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
":"NO
");
}
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
", 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 1005
using 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));
    }
};