AC 自动机_模式匹配自动机

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

学习AC自动机的前提是要会trie数和KMP字符串匹配， 它的功能是能对好多个模式串进行同时查找。

比如对4个模式串：

he

hers

his

she

在一条母串中：shejjjjj 查找每个模式串出现的次数.

我们知道KMP算法有个next数组，和KMP类似，AC自动机有一个fail指针数组，用来对整棵trie树进行滚动。

AC 自动机：

HUD 3065：

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int ch[1002*52][26],End[1002*52],cur,fail[1002*52],last[1002*52],ans[1002];

char str[2000005],str0[1002][52];

void get_fail() {

    int now,tmpFail,Next;

    queue<int> q;

    //用bfs生成fail

    //初始化队列

    for(int j=0;j<26;j++) {

        if(ch[0][j]) {

            q.push(ch[0][j]);

            fail[ch[0][j]] = 0;

            last[ch[0][j]] = 0;

        }

    }

    while(!q.empty()) {

        //从队列中拿出now

        //此时now中的fail、last已经算好了

        //下面计算的是ch[now][j]中的fail、last。

        now = q.front();q.pop();

        for(int j=0;j<26;j++) { 

            if(!ch[now][j]) continue;

            Next = ch[now][j];

            q.push(Next);

            tmpFail = fail[now];//kjkhj

            while(tmpFail&&!ch[tmpFail][j]) tmpFail = fail[tmpFail];

            fail[Next] = ch[tmpFail][j];

            last[Next] = End[fail[Next]] ? fail[Next]:last[fail[Next]];

        }

    }

}

void Find(){

    int now = 0;

    int len = strlen(str);

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

        if(str[i]<‘A’||str[i]>’Z’) {now=0;continue;}

        str[i]-=’A’;

        while(now&&!ch[now][str[i]]) now = fail[now];

        now = ch[now][str[i]];

        if(End[now]) ans[End[now]]++;

        int tmp = now;

//重要理解

//这时候已经滚到了节点now，下面就需要找出所有以now为结尾的模式串，就需要用到last数组了。Last数组保存的是以节点now为结尾的模式串。

//比如 abcd  bcd  两个模式串，abcd中d节点的last指向bcd中的d节点。

//当然两个d节点不是同一个。

//这样就能知道当滚到abcd的d节点时，我们还同时找到了bcd这个串。

//如果存在，在找到abcd的同时，我们还找到了bcd  cd  d 这三个模式串。

//事实上，下面last数组滚过的结点，在之前可能从来没有被访问过。

//《训练指南》上的代码找的是包含模式串的一段母字符串，而不是找出所有出现过的模式串。

        while(last[tmp]) {

            ans[End[last[tmp]]]++;

            tmp = last[tmp];

        }

    }

}

int main(){

    int n,now;

    while(scanf(“%d”,&n)!=EOF){

    memset(ch,0,sizeof(ch));

    memset(End,0,sizeof(End));

    memset(ans,0,sizeof(ans));

    memset(last,0,sizeof(last));

    cur = 1;

    int len;

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

        scanf(“%s”,str0[i]);

        len = strlen(str0[i]);

        now = 0;

        for(int j=0;j<len;j++) {

            str0[i][j]-=’A’;

            if(ch[now][str0[i][j]]==0) ch[now][str0[i][j]] = cur++;

            now = ch[now][str0[i][j]];

            str0[i][j]+=’A’;

        }

        End[now] = i;

    }

    get_fail();

    scanf(“%s”,str);

    Find();

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

        if(ans[i])

            printf(“%s: %d\n”,str0[i],ans[i]);

    }

    }

}