HDU 1671 Phone List (Trie·数组实现)

链接：http://blog.csdn.net/acvay/article/details/47089657

题意给你一组电话号码判断其中是否有某个电话是另一个电话的前缀

字典树的基础应用可以先把所有电话存进Trie 标记每个电话的结束字符然后再查询每个号码看中途是否有结束标记有的话就说明有号码是这个号码的前缀了

实际上插入完成就能知道是否有号码是另一个号码的前缀了假设A是B的前缀

若A在B之前插入那么插入B的时候会遇到A的结束标记

弱A在B之后插入那么A插入完成之后的结点还有非空的孩子结点

这样就只用在每次插入时判断就行了可以省掉查询这一步

指针和动态内存分配实现字典更容易些但在有多组样例的时侯不释放内存会导致MLE 释放内存又要多花费不必要的时间可能导致TLE 所以用数组实现比较好

#include<cstdio>

#include<cstring>

using namespace std;

const int N = ;

char tel[N][];

int trie[N * ][], L;

bool end[N * ], flag;

void initTrie() {

    L = ;

    memset(trie, , sizeof(trie));

    memset(end, , sizeof(end));

}

void _insert(char *s) {

    int r = , i = , j;

    while (s[i]) {

        if (end[r]) flag = false;

        j = s[i++] - '';

        if (!trie[r][j])

            trie[r][j] = L++;

        r = trie[r][j];

    }

    for (int i = ; i < ; i++) {

        if (trie[r][i]) flag = ;

        end[r] = ;

    }

}

int main() {

    int T, n;

    scanf("%d", &T);

    while (T--) {

        initTrie();

        scanf("%d", &n);

        flag = true;

        for (int i = ; i < n; ++i) {

            scanf("%s", tel[i]);

            _insert(tel[i]);

        }

        puts(flag ? "YES" : "NO");

    }

    return ;

}

巴特西

HDU 1671 Phone List (Trie·数组实现)

最新文章

热门文章