迷之好奇 —静态字典树

╰+攻爆jí腚メ 2022-07-12 04:45 174阅读 0赞

think:  
1 今天学习字典树，一开始学哥讲的时候感觉字典树模板性比较强，下午晚上敲了2个字典树的题目，迷之好奇这个题目一开始用即类似静态数组又不是完全是静态数组来做，编译通过样本数据也对，但是一直wrong answer，感觉有点心态失衡，便从网上搜了下代码，跟着敲下来后感觉对通过静态数组存储的静态字典树有点明白了，但是还是不知道一开始的题目为什么错误，只能先记录下来了。呜呜呜。

[sdut原题链接][sdut]

迷之好奇  
Time Limit: 2000MS Memory Limit: 65536KB

Problem Description  
FF得到了一个有n个数字的集合。不要问我为什么，有钱，任性。  
FF很好奇的想知道，对于数字x，集合中有多少个数字可以在x前面添加任意数字得到。  
如，x = 123，则在x前面添加数字可以得到4123，5123等。

Input  
多组输入。  
对于每组数据  
首先输入n(1<= n <= 100000)。  
接下来n行。每行一个数字y(1 <= y <= 100000)代表集合中的元素。  
接下来一行输入m(1 <= m <= 100000),代表有m次询问。  
接下来的m行。  
每行一个正整数x(1 <= x <= 100000)。

Output  
对于每组数据，输出一个数字代表答案。

Example Input  
3  
12345  
66666  
12356  
3  
45  
12345  
356

Example Output  
1  
0  
1

Hint

Author  
zmx

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    int top;
    struct node
    {
        int next[26];
        int flag;
        int cnt;
    }st[6000000];
    int Creat()
    {
        memset(st[top].next, -1, sizeof(st[top].next));
        st[top].flag = 0;
        st[top].cnt = 0;
        top++;
        return top-1;
        ///return top++;
    }
    void Insert(int rt, char *s)
    {
        int len = strlen(s);
        for(int i = len-1; i >= 0; i--)
        {
            int t = s[i] - '0';
            if(st[rt].next[t] == -1)
            {
                st[rt].next[t] = Creat();
            }
            st[rt].flag++;
            rt = st[rt].next[t];
        }
    }
    int Search(char *s, int rt)
    {
        int len = strlen(s);
        for(int i = len-1; i >= 0; i--)
        {
            int t = s[i] - '0';
            if(st[rt].next[t] == -1)
            {
                return 0;
            }
            rt = st[rt].next[t];
        }
        return st[rt].flag;
      //return st[rt].cnt;
    }
    int main()
    {
        int n, m, rt;
        char s[14];
        while(scanf("%d", &n) != EOF)
        {
            top = 0;
            rt = Creat();
            while(n--)
            {
                scanf("%s", s);
                Insert(rt, s);
            }
            scanf("%d", &m);
            while(m--)
            {
                scanf("%s", s);
                printf("%d\n", Search(s, rt));
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 416ms
    Take Memory: 1384KB
    Submit time: 2017-02-10 20:47:54
    ****************************************************/

以下wrong answer代码

/* 字典树的逆序应用*/
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MAXC 10
    #define MAXN 600000
    typedef struct node
    {
        int cnt;
        int flag;//flag记录每个结点在字符串插入时字符串经过的次数
        struct node *next[MAXC];
    }Trie;
    Trie trie[MAXN];
    int top;
    Trie * Build()//建立结点
    {
        Trie *p = &trie[top++];
        p->cnt = 0;
        p->flag = 0;
        for(int i = 0; i < MAXC; i++)
            p->next[i] = NULL;
        return p;
    }
    Trie * Creat()//初始化
    {
        top = 0;
        return Build();
    }
    void Insert(Trie *root, char *str)//插入操作
    {
        int len = strlen(str);
        Trie *p = root;
        for(int i = len-1; i >= 0; i--)//(逆序插入)
        {
            int t = str[i] - '0';
            if(p->next[t] == NULL)
                p->next[t] = Build();
            p = p->next[t];
            p->flag++;
        }
        p->cnt++;
    }
    int Find1(Trie *root, char *str)//判断是否是某一字符串的子串
    {
        int len = strlen(str);
        Trie *p = root;
        for(int i = len-1; i >= 0; i--)
        {
            int t = str[i] - '0';
            if(p->next[t] == NULL)
                return p->cnt;
            p = p->next[t];
        }
        return p->cnt;
    }
    int Find2(Trie *root, char *str)//得到最后字符所在结点的flag记录值
    {
        int len = strlen(str);
        Trie *p = root;
        for(int i = len-1; i >= 0; i--)
        {
            int t = str[i] - '0';
            if(p->next[t] == NULL)
                break;
            //p->flag++;
            p = p->next[t];
            //p->flag++;
        }
        return p->flag;
    }
    int main()
    {
        int n, m;
        char str[9];
        while(scanf("%d", &n) != EOF)
        {
            Trie *root;
            root = Creat();//初始化+建立
            while(n--)
            {
                scanf("%s", str);
                Insert(root, str);//字符串插入
            }
            scanf("%d", &m);
            while(m--)
            {
                scanf("%s", str);
                if(Find1(root, str) == 0)//如果是某一字符串的子串，则Find1返回值为0
                    printf("%d\n", Find2(root, str));//Find2返回记录值flag
                else
                    printf("0\n");
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Wrong Answer
    Take time: 372ms
    Take Memory: 1380KB
    Submit time: 2017-02-10 19:44:40
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2009/pid/3039