首页 > 代码库 > POJ - 3630 代码

POJ - 3630 代码

2024-07-13 01:37:00   223人阅读

Trie的简单应用，只涉及插入字符串的操作。

需要注意的是，输入数据有T组，在处理每一组数据之前都要初始化root，由于忽视了这一点WA了n次。

还有一点就是，在发现一组数据答案为“NO”之后，仍然要读完这组数据的字符串。在这一点上也WA了好多次= =

 

另外，本题大概需要建立4000000个节点，如果采用动态空间建点会TLE。

看来malloc操作确实是很慢啊。

所以提前开一个大的数组空间，静态的就好了。

 

代码如下：

/*Author : Magician Van*/#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>using namespace std;const int MaxNext = 10 + 2, MaxL = 10 + 2, MaxNode = 100000 + 5;int T, n, top;char Str[MaxL];bool Wrong = false;typedef struct TrieNode {    bool isStr;    TrieNode *Next[MaxNext];} Trie;Trie Ta[MaxNode];void Insert(Trie *root, char *S, int len){    if (root == NULL || len == 0) return;    Trie *p = root;    int sum = 0;    for (int i = 0; i <= len - 1; i++)    {        if (p -> Next[S[i] - ‘0‘] == NULL)        {            Trie *temp = &Ta[++top];            temp -> isStr = false;            for (int j = 0; j <= 9; j++) temp -> Next[j] = NULL;            p -> Next[S[i] - ‘0‘] = temp;         }        else sum++;        p = p -> Next[S[i] - ‘0‘];        if (p -> isStr)         {            Wrong = true;            return;        }    }    p -> isStr = true;    if (sum == len) Wrong = true;} int main(){    scanf("%d", &T);    for (int t = 1; t <= T; t++)    {        top = 0;                Trie *root = &Ta[++top];        for (int i = 0; i <= 9; i++) root -> Next[i] = NULL;        root -> isStr = false;        Wrong = false;        scanf("%d", &n);        for (int i = 1; i <= n; i++)         {            scanf("%s", Str);            if (!Wrong) Insert(root, Str, strlen(Str));        }        if (Wrong) printf("NO\n");        else printf("YES\n");    }    return 0;}


联系
我们