HDU 1251 统计难题(字典树)

Description:

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

Input:

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input:

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output:

2
3
1
0

题目链接

字典树模板题，每层使用一个Cnt变量记录字符串数量。

PS:此AC代码交G++会MLE，交C++即可AC。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 26;

struct Trie {
    Trie *Next[maxn];
    int Cnt;
    Trie() {
        for (int i = 0; i < maxn; ++i) {
            Next[i] = NULL;
        }
        Cnt = 0;
    }
};

Trie *Root;

void InsertTrie(char *Str) {
    int Len = strlen(Str);
    Trie *P = Root;
    for (int i = 0; i < Len; ++i) {
        int ID = Str[i] - '0';
        if (P -> Next[ID] == NULL) {
            P -> Next[ID] = new Trie;
        }
        P = P -> Next[ID];
        P -> Cnt++;
    }
}

int FindTrie(char *Str) {
    int Len = strlen(Str);
    Trie *P = Root;
    for (int i = 0; i < Len; ++i) {
        int ID = Str[i] - '0';
        if (P -> Next[ID] == NULL) {
            return 0;
        }
        P = P -> Next[ID];
    }
    return P -> Cnt;
}

void DeleteTrie(Trie *Node) {
    if (Node == NULL) {
        return;
    }
    for (int i = 0; i < maxn; ++i) {
        if (Node -> Next[i] != NULL) {
            DeleteTrie(Node -> Next[i]);
        }
    }
    free(Node);
}

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1, N; Case <= T; ++Case) {
        scanf("%d", &N);
        DeleteTrie(Root);
        Root = new Trie;
        char Str[maxn];
        bool Flag = 1;
        for (int i = 0; i < N; ++i) {
            scanf("%s", Str);
            if (FindTrie(Str) > 0) {
                Flag = 0;
            }
            if (!Flag) {
                continue;
            }
            InsertTrie(Str);
        }
        if (Flag) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}