hods2896(AC自动机）

AC自动机：

关键点是字符失败指针为父亲节点的失败指针的儿子字母是否和该字符相同，不相同再找失败指针的失败指针的儿子，这样保证了这两个相同字符之前的字符，也就是父亲字符要不没有要不相同，代码我加了注释好懂一点

思路：前面的操作跟常规的AC自动机一样，只是我们需要在结构体里加入一些额外的保存信息，比如当前字符串的编号，是否被遍历过等等

因为后面需要跟多个串进行比较，所以不能直接把权值赋为-1，所以我们多加一个标记，每次标记为i即可（每一次进入新的字符串，i都会加一，但是在当前的字符串，i标记了后就不能再进去了）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespacestd;

#define N 300

#define M 10050

char s[N],str[M];

int a[M],t;

struct Node

{

    structNode *next[128];

    structNode *fail;

    int num,flag;

    void init()

    {

        for(int i=0; i<128; i++)

            next[i]=NULL;

        fail=NULL;

        num=0;

        flag=0;

    }

}*root;

void Insert(int id)//构造树

{

    Node *p=root;

    int len=strlen(s);

    for(int i=0; i<len; i++)

    {

        int pos=s[i];

        if(p->next[pos]==NULL)

        {

            p->next[pos]=newNode;

            p->next[pos]->init();

        }

        p=p->next[pos];

    }

    p->num=id;//结点值为该单词的序号

}

void getfail()

{

    Node *p=root,*now,*son;

    queue<Node *>que;

    que.push(p);

    while(!que.empty())

    {

        now=que.front();

        que.pop();

        for(int i=0; i<128; i++)

        {

            son=now->next[i];

            if(son!=NULL)

            {

                if(now==root)

                    son->fail=root;//第一层

                else

                {

                    p=now->fail;//p为now的前缀链接

                    while(p)//如果到root退出，不明白为什么root为空

                    {

                        if(p->next[i])//p的儿子有和son相同的字符

                        {

                            son->fail=p->next[i];//确定son的前缀链接

                            break;

                        }

                        p=p->fail;//找链接的链接直到root

                    }

                    if(!p)//p为root

                        son->fail=root;

                }

                que.push(son);

            }

        }

    }

}

void query(int id)

{

    Node *p=root,*temp;

    int len=strlen(str);

    for(int i=0; i<len; i++)

    {

        int pos=str[i];

        while(!p->next[pos]&&p!=root)//p->next已没值，查找p的fail

            p=p->fail;

        p=p->next[pos];

        if(!p)

            p=root;//感觉有点鸡肋

        temp=p;

        while(temp!=root)

        {

            if(t>=3)

                break;

            if(temp->num>0&&temp->flag!=id)//到达一个结点

            {

                a[t++]=temp->num;

                temp->flag=id;

            }

            else

                break;

            temp=temp->fail;//这一句不太懂

        }

        if(t>=3)break;

    }

}

int main()

{

    int n,m;

    while(~scanf("%d",&n))

    {

        root=newNode;

        root->init();

        getchar();

        for(int i=1; i<=n; i++)

        {

            gets(s);

            Insert(i);

        }

        getfail();

        scanf("%d",&m);

        int ans=0;

        getchar();

        for(int k=1; k<=m; k++)

        {

            t=0;

            gets(str);

            query(k);

            if(t>0)

            {

                ans++;

                sort(a,a+t);

                printf("web %d: ",k);

                for(int i=0; i<t-1; i++)

                    printf("%d ",a[i]);

                printf("%d\n",a[t-1]);

            }

        }

        printf("total: %d\n",ans);

    }

    return0;

}