关于Trie的空间问题

学术版

WhiteNight__ @ 2024-11-28 13:21:33

题目见P2580

MLE提交记录

代码大概是这样的

我也尝试过用数组替换vector，但在数组大小为 5\times10^5 时 8 , 9 RE；在 6\times10^5 时 8 , 9 MLE。但我看其他题解可以用 5\times10^5 过这一道题，并且空间小8倍左右。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int n , m;

struct Trie {
    int cnt;
    struct Table {
        bool isend;
        int t[27];
        Table ()
        {
            this->isend = false;
            memset (t , 0 , sizeof t);
        }
    };

    vector <Table> tr;

    Trie ()
    {
        cnt = 0;
        tr.clear();
        tr.push_back(Table());
    }

    void Insert (string x)
    {
        int lenx = x.size();
        int root(0);
        for(int i = 0 ; i < lenx ; i ++)
        {
            int fx = x.at(i) - 'a' + 1;
            if(tr.at(root).t[fx] == 0)
            {
                ++ cnt;
                tr.push_back(Table());
                tr.at(root).t[fx] = cnt;
            }
            root = tr.at(root).t[fx];
//          printf("root = %d  tr.s = %d  cnt = %d\n",root,(int)tr.size(),cnt);
        }
        tr.at(root).isend = true;
    }

    bool Find (string x)
    {
        int lenx = x.size();
        int root(0);
        for(int i = 0 ; i < lenx ; i ++)
        {
            int fx = x.at(i) - 'a' + 1;
            if(tr.at(root).t[fx] == 0) return false;
            root = tr.at(root).t[fx];
        }
        return tr.at(root).isend;
    }
}in , pd;

int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    {
        string s;
        cin >> s;
        in.Insert (s);
    }
    scanf("%d",&m);
    for(int i = 1 ; i <= m ; i ++)
    {
        string s;
        cin >> s;
        if(in.Find(s) == false)
        {
            printf("WRONG\n");
        }
        else
        {
            if(pd.Find(s) == false)
            {
                printf("OK\n");
            }
            else printf("REPEAT\n");
        }
        pd.Insert(s);
    }
    return 0;
}

by Lybei @ 2024-11-28 13:23:17

大概是实现写错了罢

by pig1121 @ 2024-11-28 13:41:12

@WhiteNight__ 你并不需要开两颗 trie，只需要每个节点两个标记，一个记录是否是结尾，一个记录有没有被点过（其实可以合并成一个）

by movefast @ 2024-11-28 13:45:11

@WhiteNight__ 为什么不用链表

by WhiteNight__ @ 2024-11-28 13:47:52

@pig1121

谢谢，但改完之后空间仍然被卡。

记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int n , m;

struct Trie {
    int cnt;
    struct Table {
        bool isend;
        bool tags;
        int t[27];
        Table ()
        {
            this->isend = false;
            this->tags = false;
            memset (t , 0 , sizeof t);
        }
    };

    vector <Table> tr;

    Trie ()
    {
        cnt = 0;
        tr.clear();
        tr.push_back(Table());
    }

    void Insert (string x)
    {
        int lenx = x.size();
        int root(0);
        for(int i = 0 ; i < lenx ; i ++)
        {
            int fx = x.at(i) - 'a' + 1;
            if(tr.at(root).t[fx] == 0)
            {
                ++ cnt;
                tr.push_back(Table());
                tr.at(root).t[fx] = cnt;
            }
            root = tr.at(root).t[fx];
            //          printf("root = %d  tr.s = %d  cnt = %d\n",root,(int)tr.size(),cnt);
        }
        tr.at(root).isend = true;
    }

    int Find (string x)
    {
        int lenx = x.size();
        int root(0);
        for(int i = 0 ; i < lenx ; i ++)
        {
            int fx = x.at(i) - 'a' + 1;
            if(tr.at(root).t[fx] == 0) return false;
            root = tr.at(root).t[fx];
        }
        if(tr.at(root).isend == false) return 0;

        else if(tr.at(root).tags == false)
        {
            tr.at(root).tags = true;
            return 1;
        }

        return 2;
    }
}ing;

int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; i ++)
    {
        string s;
        cin >> s;
        ing.Insert (s);
    }
    scanf("%d",&m);
    for(int i = 1 ; i <= m ; i ++)
    {
        string s;
        cin >> s;
        int Ans = ing.Find(s);
        if(Ans == 0)
        {
            printf("WRONG\n");
        }
        else
        {
            if(Ans == 1)
            {
                printf("OK\n");
            }
            else printf("REPEAT\n");
        }
        ing.Insert(s);
    }
    return 0;
}

by WhiteNight__ @ 2024-11-28 13:49:46

@pig1121

额好像是我写岔了。

ing.Insert(s);

放 Ans == 1 里面就过了。

谢谢。

by WhiteNight__ @ 2024-11-28 13:52:49

@movefast

懒得写链表了就用vector了