发布于 由itewqq

[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora

https://cn.vjudge.net/problem/HDU-3695

跟2222几乎一样，求文本中出现了多少个模式串，但是数据量变大了，5e6的长度。这时候用原来的写法已经会tle了，看到别人说用打标记的方式记录trie上一个节点有没有走过，一开始是不理解的，为什么这么做是正确的？后来想了想，AC自动机的算法确定了一个起点之后，沿着fail回溯的路径便已经确定（神奇），所以这条路上被走过的单词尾，再走的时候就会重复，而我们可以简单的把走过的节点计数标志变为-1，而在之后的过程中再遇到就可以不用管这个节点及其之后所有的节点了。注意这个是在while一开始就得判断。

WA的话，是从带括号的那个原串解压过后忘了在最后加’\0’。。。emmmm以后试验这种一定要从大到小试验数据。还有就是模板一定要用自己熟悉的。。原来以为这题问题在于kuangbin的板子不够快后来发现是没标记。。第二个是一开始没意识到q可以不止1位。。

 #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=5e6+2e5+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=6e6+5;

int ans,len1;

struct Trie
{
    int nxt[maxnode][26],fail[maxnode],isend[maxnode],leng[maxnode];//pos[maxn];
    //bool  vis[maxnode];
    int root,idx;

    int newnode()
    {
        for (int i=0; i<26; i++)
            nxt[idx][i]=-1;
        isend[idx]=0;
        //leng[idx++]=0;
        idx++;
        return idx-1;
    }

    void init()
    {
        idx=0;
        root=newnode();
        //memset(vis,0,sizeof(maxnode));
    }

    void insert(char buf[])
    {
        //cout<<"buf   "<Q;
        fail[root]=root;
        for(int i=0; i<26; i++)
        {
            if(nxt[root][i]==-1)
                nxt[root][i]=root;
            else
            {
                fail[nxt[root][i]]=root;
                Q.push(nxt[root][i]);
            }
        }
        while(!Q.empty())
        {
            now=Q.front();
            Q.pop();
            for (int i=0; i<26; i++)
                if(nxt[now][i]==-1)
                    nxt[now][i]=nxt[fail[now]][i];
                else
                {
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    Q.push(nxt[now][i]);
                }
        }
    }

    void query(char buf[])
    {
        len1=strlen(buf);
        int now=root,temp=root;
        for (int i=0;i

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。