首页 > 代码库 > luogu P2353 背单词

luogu P2353 背单词

2024-10-08 01:09:39   211人阅读

二次联通门 : luogu P2353 背单词

 

 

一眼看过去， 卧槽，AC自动机板子题

写完后T成SB

卧槽10^6 做个篮子啊

重构思路。。。

恩。。Hash + 莫队。。。

恶心啊。。

 

找xxy dalao， AC自动机 + 前缀和

码完WA成SB

去群里找dalao

大佬告诉了我前缀和的正确使用姿势。。。

 

然后就依然WA成SB

 

技术分享

 

 

 做个毛线

 

贴一个AC自动机的30代码

 

#include <cstdio>
#include <cstring>
#include <queue>

#define Max 3000090

void read (int &now)
{
    now = 0;
    register char word = getchar ();
    while (word < ‘0‘ || word > ‘9‘)
        word = getchar ();
    while (word >= ‘0‘ && word <= ‘9‘)
    {
        now = now * 10 + word - ‘0‘;
        word = getchar ();
    }
}

char __txt[Max];

struct T_D
{
    T_D *child[26];

    T_D *Fail;
    int Count;
    
    int number;
    T_D ()
    {
        for (int i = 0; i < 26; i ++)
            this->child[i] = NULL;
        
        Count = 0;
        Fail = NULL;
        number = 0;
    }
};

int List[Max << 1];
int List_Cur;

bool visit[Max];

class AC_Type
{

    private :

        T_D *Root;
        int Trie_Count;

    
    public :

        void Insert (char *key)
        {
            T_D *now = Root;

            int Len = strlen (key);
            int Id;

            for (int i = 0; i < Len; i ++)
            {
                Id = key[i] - ‘a‘;
                if (now->child[Id] == NULL)
                {
                    now->child[Id] = new T_D;
                    now->child[Id]->number = ++ Trie_Count;
                }

                now = now->child[Id];
            }
            now->Count ++;
        }

        AC_Type ()
        {
            Trie_Count = 0;
            Root = new T_D ;
            Root->number = ++ Trie_Count;
        }

        void Build_AC ()
        {
            std :: queue <T_D *> Queue;

            Queue.push (Root);
            
            T_D *now, *pos;
            while (!Queue.empty ())
            {
                now = Queue.front ();
                Queue.pop ();

                pos = NULL;

                for (int i = 0; i < 26; i ++)
                {
                    if (now->child[i] == NULL)
                        continue;
                    if (now == Root)
                        now->child[i]->Fail = Root;
                    else
                    {
                        for (pos = now->Fail; pos; pos = pos->Fail)
                            if (pos->child[i])
                            {
                                now->child[i]->Fail = pos->child[i];
                                break;
                            }
                        if (pos == NULL)
                            now->child[i]->Fail = Root;
                    }
                    Queue.push (now->child[i]);
                }
            }
        }

        int Query (int x, int y)
        {
            T_D *now, *pos;
            
            int Id ;
            now = Root;
            int res = 0;
            
            for (int i = x; i <= y; i ++)
            {
                Id = __txt[i] - ‘a‘;
                for (; now != Root && now->child[Id] == NULL; now = now->Fail);
                
                now = now->child[Id];
                if (now == NULL)
                    now = Root;

                for (pos = now; pos != Root && !visit[pos->number]; pos = pos->Fail)
                {
                    res += pos->Count;
                    visit[pos->number] = true;
                    List[++ List_Cur] = pos->number;
                }

                for (int j = 1; j <= List_Cur; j ++)
                    visit[List[j]] = false;

                List_Cur = 0;
        
            }
        
            return res;
        }

};

AC_Type Make;

int N, Q;
char line[Max];

int main (int argc, char *argv[])
{
    read (N);
    read (Q);
    scanf ("%s", __txt);
    
    for (int i = 1; i <= N; i ++)
    {
        scanf ("%s", line);
        Make.Insert (line);
    }
    
    Make.Build_AC ();
    
    for (int x, y; Q --; )
    {
        read (x);
        read (y);
                    
        printf ("%d\n", Make.Query (-- x, -- y));
    }

    return 0;
}

 

 

 再贴个AC自动机思路正确但由于细节问题WA成dog的代码

 

#include <cstdio>
#include <cstring>
#include <queue>

#define Max 1000090

#define DEBUG for (int i = 1; i <= strlen (__txt); i ++)\
                printf ("%d  ", __sum[i]);                putchar (‘\n‘);
                
void read (int &now)
{
    now = 0;
    register char word = getchar ();
    while (word < ‘0‘ || word > ‘9‘)
        word = getchar ();
    while (word >= ‘0‘ && word <= ‘9‘)
    {
        now = now * 10 + word - ‘0‘;
        word = getchar ();
    }
}

char __txt[Max];

struct T_D
{
    T_D *child[26];

    T_D *Fail;
    int Count;
    
    int number;
    T_D ()
    {
        for (int i = 0; i < 26; i ++)
            this->child[i] = NULL;
        
        Count = 0;
        Fail = NULL;
        number = 0;
    }
};

int __sum[Max];

class AC_Type
{

    private :

        T_D *Root;
        int Trie_Count;

    
    public :

        void Insert (char *key)
        {
            T_D *now = Root;

            int Len = strlen (key);
            int Id;

            for (register int i = 0; i < Len; i ++)
            {
                Id = key[i] - ‘a‘;
                if (now->child[Id] == NULL)
                {
                    now->child[Id] = new T_D;
                    now->child[Id]->number = ++ Trie_Count;
                }

                now = now->child[Id];
            }
            now->Count ++;
        }

        AC_Type ()
        {
            Trie_Count = 0;
            Root = new T_D ;
            Root->number = ++ Trie_Count;
        }

        void Build_AC ()
        {
            std :: queue <T_D *> Queue;

            Queue.push (Root);
            
            T_D *now, *pos;
            while (!Queue.empty ())
            {
                now = Queue.front ();
                Queue.pop ();

                pos = NULL;

                for (register int i = 0; i < 26; i ++)
                {
                    if (now->child[i] == NULL)
                        continue;
                    if (now == Root)
                        now->child[i]->Fail = Root;
                    else
                    {
                        for (pos = now->Fail; pos; pos = pos->Fail)
                            if (pos->child[i])
                            {
                                now->child[i]->Fail = pos->child[i];
                                break;
                            }
                        if (pos == NULL)
                            now->child[i]->Fail = Root;
                    }
                    Queue.push (now->child[i]);
                }
            }
        }

        int Query ()
        {
            T_D *now, *pos;
            
            int Id ;
            now = Root;
            int res = 0;
            int Len = strlen (__txt);
            
            for (register int i = 0; i < Len; i ++)
            {
                Id = __txt[i] - ‘a‘;
                for ( ; now != Root && now->child[Id] == NULL; now = now->Fail);
                
                now = now->child[Id];
                if (now == NULL)
                    now = Root;

                for (pos = now; pos != Root && pos->Count >= 0; pos = pos->Fail)
                {
                    __sum[i + 1] += pos->Count;
                    pos->Count = -1;
                }
                __sum[i + 1] += __sum[i];
        
            }
        
            return res;
        }

};

AC_Type Make;

int N, Q;
char line[Max];

int length[Max];

int main (int argc, char *argv[])
{

    read (N);
    read (Q);
    scanf ("%s", __txt);
    
    for (int i = 1; i <= N; i ++)
    {
        scanf ("%s", line);
        Make.Insert (line);
        length[i] = strlen (line);
    }
    
    Make.Build_AC ();
    Make.Query ();
       register int Answer, now;
       
    for (int x, y; Q --; )
    {
        Answer = 0;
        
        read (x);
        read (y);
        
        for (int i = 1; i <= N; i ++)
            Answer += (__sum[y - length[i]] - __sum[x - 1]);
        
        printf ("%d\n", Answer);
    }

    return 0;
}

 

 

最后再贴个正解。。。。是我想麻烦了。。kmp或者hash都可以。。

 

luogu P2353 背单词


联系
我们