「POJ 3630」Phone List - Trie

发表于 | 分类于

给 个字符串，求有没有一个字符串是另一个字符串的前缀。

链接

POJ 3630

题解

建立 Trie，依次插入每个字符串，在插入时判断。

判断当前字符串的前缀已被插入：插入时在路径上遇到一个单词节点。

判断当前字符串是已插入字符串的前缀：插入时最后一个节点已存在。

为防止 TLE，需要内存池。

代码

#include <cstdio>
#include <cstring>
#include <new>

const int MAXN = 10000;

struct Node {
    Node *ch[10];
    bool isWord;

    Node(bool isWord = false) : isWord(isWord) {
        for (int i = 0; i < 10; i++) ch[i] = NULL;
    }
} *root, _pool[MAXN * 10], *_curr;

bool insert(char *begin, char *end) {
    Node **v = &root;
    bool res = false;
    for (char *p = begin; p != end; p++) {
        if (!*v) *v = new (_curr++) Node(false);
        else if ((*v)->isWord) res = true;

        v = &(*v)->ch[*p];
    }
    if (!*v) *v = new (_curr++) Node(true);
    else res = true;

    return res;
}

void init() {
    root = NULL;
    _curr = _pool;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);

        init();

        bool ans = false;
        while (n--) {
            static char s[10 + 2];
            scanf("%s", s + 1);

            int len = strlen(s + 1);
            for (int i = 1; i <= len; i++) s[i] -= '0';

            if (insert(s + 1, s + len + 1)) ans = true;
        }

        puts(ans ? "NO" : "YES");
    }

    return 0;
}