absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-2] BZOJ 4034
[破碎的状态] [-2] POJ 3693

[破碎的状态] [-2] Vijos 1951

absi2011 posted @ Jul 20, 2016 09:29:28 PM in 刷题记录 with tags vijos AC自动机 小高考 , 251 阅读

一个AC自动机的模版题= =

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct node
{
    bool visit;
    node * fail;
    node * ch[4];
};
node * new_node()
{
    static node a[10000005];
    static int top=0;
    a[top].visit=0;
    a[top].fail=0;
    a[top].ch[0]=0;
    a[top].ch[1]=0;
    a[top].ch[2]=0;
    a[top].ch[3]=0;
    return &a[top++];
}
int code(char x)
{
    if (x=='S') return 1;
    if (x=='N') return 2;
    if (x=='E') return 3;
    if (x=='W') return 0;
    return -1;
}
char a[10000005];
char b[100005][105];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    gets(a);
    gets(a);
    int i;
    node * root=new_node();
    for (i=0;i<m;i++)
    {
        gets(b[i]);
        int j;
        node * now=root;
        for (j=0;b[i][j]!='\0';j++)
        {
            if (now->ch[code(b[i][j])]==0)
            {
                now->ch[code(b[i][j])]=new_node();
            }
            now=now->ch[code(b[i][j])];
        }
    }
    static node * que[10000005];
    int front=0,rail=1;
    que[0]=root;
    root->fail=root;
    for (;front<rail;front++)
    {
        node * t=que[front];
        int i;
        for (i=0;i<4;i++)
        {
            if (t->ch[i]==0)
            {
                if (t==root)
                {
                    t->ch[i]=root;
                }
                else
                {
                    t->ch[i]=t->fail->ch[i];
                }
            }
            else
            {
                que[rail++]=t->ch[i];
                if (t==root)
                {
                    t->ch[i]->fail=root;
                }
                else
                {
                    t->ch[i]->fail=t->fail->ch[i];
                }
            }
        }
    }
    node * now=root;
    for (i=0;a[i]!='\0';i++)
    {
        now=now->ch[code(a[i])];
        now->visit=true;
    }
    for (i=rail-1;i>=0;i--)
    {
        que[i]->fail->visit|=que[i]->visit;
    }
    for (i=0;i<m;i++)
    {
        int j;
        node * now=root;
        for (j=0;b[i][j]!='\0';j++)
        {
            now=now->ch[code(b[i][j])];
            if (!now->visit) break;
        }
        printf("%d\n",j);
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter