[AC自动机][模板] HDU5880 Family View

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

AC自动机模板题，不过判断是否是禁忌串内的这种标记方法还是值得一看的。

主要是理解了AC自动机的板子。。当时比赛没有把这个题写出来也是挫了，其实就是模板题。有一个需要注意的地方是如果禁忌串互相包含怎么操作，这里参考的大佬代码用的pos-1和+1标记是否在括号内的做法，很舒服。

错误的话，把Trie开到main里RE。。本地都RE，然后每个test都要换行，忘了这个PE了一发。


//#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=1e6+100;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=1e6+5;


char tmp[maxn];

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

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

    void init()
    {
        idx=0;
        root=newnode();
    }

    void insert(char buf[])
    {
        int len=strlen(buf);
        int now=root;
        for (int i=0; iQ;
        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())
        {
            int 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[])
    {
        memset(pos,0,sizeof(pos));
        int len=strlen(buf);
        int now=root;
        //int res=0;
        for (int i=0;i='A')
                now=nxt[now][buf[i]-'A'];
            else if(buf[i]<='z'&&buf[i]>='a')
                now=nxt[now][buf[i]-'a'];
            else continue;
            int temp=now;
            while(temp!=root)
            {
                if(isend[temp])
                {
                    pos[i+1]+=-1;
                    pos[i-leng[temp]+1]+=1;
                }
                temp=fail[temp];
            }
        }
        int cnt=0;
        for (int i=0;i0)
                putchar('*');
            else
                putchar(buf[i]);
        }
        puts("");
    }
};

Trie tree;//not in main!

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        tree.init();
        scanf("%d",&n);
        getchar();
        for (int i=0;i

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

发表回复 取消回复

发表回复取消回复