字符串——AC自动机

一、前言
二、思路
三、代码
四、参考资料

一、前言

以前一直没学AC自动机，主要是被名字吓到了，自动AC，这么强的名字肯定很难，学了后才发现，其实不难。

AC自动机并不是Acept automaton，而是Aho-Corasick automaton，A和C分别取自其发明者的姓名，有点巧。

那么，它是干什么的呢？

简而言之，是在文本串中寻找多个模板串的算法。

是不是类似于KMP算法？

KMP算法是在文本串中寻找一个模板串，那么，如果用KMP解决AC自动机的题，其时间复杂度是多少呢？

O(x*(n+m))，x是模板串的数量，n是文本串长度，m是模板串平均长度

显然，相较于暴力而言还算不错，但是当模板串过多时，这算法也不够优雅。

这时候就是AC自动机的闪亮登场了，其时间复杂度仅为O(n+x*m)。也就是说，我们仅需遍历一次文本串即可

二、思路

AC自动机 = KMP + Trie

KMP可以参考博文kmp算法讲解及其模板

Trie的话，本人暂时没写过博文，不过这部分也不算难，可自行百度。

至于AC自动机，感觉写起来有点麻烦，有点犯懒了，而且刚学，不算精通，暂时跳过。

三、代码

hdu 2222模板题

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn =  5e5+9;

char s[maxn<<1];

int trie[maxn][26]; //字典树

int cntword[maxn];  //记录该单词出现次数

int fail[maxn];     //失败时的回溯指针

int cnt,n;

int newNode(){//插入节点

	cnt++;

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

		trie[cnt][i] = 0;

	cntword[cnt] = fail[cnt] = 0;

	return cnt;

}

void init(){//初始化

	cnt = -1;

	cnt = newNode();

}

void insertWords(){//单纯是Trie部分内容，建立字典树

    int root = 0;

    int len = strlen(s);

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

        int next = s[i] - 'a';

        if(!trie[root][next])

            trie[root][next] = newNode();

        root = trie[root][next];

    }

    cntword[root]++;      //当前节点单词数+1

}

void getFail(){

    queue <int>q;

    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列

        if(trie[0][i]){

            fail[trie[0][i]] = 0;

            q.push(trie[0][i]);

        }

    }

//fail[now]    ->当前节点now的失败指针指向的地方

////tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]

    while(!q.empty()){

        int now = q.front();

        q.pop();

        for(int i=0;i<26;i++){      //查询26个字母

            if(trie[now][i]){

                //如果有这个子节点为字母i+'a',则

//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)

                //有点绕,为了方便理解特意加了括号

                fail[trie[now][i]] = trie[fail[now]][i];

                q.push(trie[now][i]);

            }

            else//否则就让当前节点的这个子节点

                //指向当前节点fail指针的这个子节点

                trie[now][i] = trie[fail[now]][i];

        }

    }

}

int query(){

    int now = 0,ans = 0;

    int len = strlen(s);

    for(int i=0;i<len;i++){    //遍历文本串

        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找

        for(int j=now;j && cntword[j]!=-1;j=fail[j]){

            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).

            ans += cntword[j];

            cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算

        }

    }

    return ans;

}

int main() {

	int t;

	cin >> t;

	while(t--){

		init();

	    cin >> n;

	    for(int i=0;i<n;i++){//插入模板串

	        scanf("%s",s);

	        insertWords();

	    }

	    fail[0] = 0;

	    getFail();

	    scanf("%s",s);

	    cout << query() << endl;

	}

    return 0;

}

四、参考资料

https://blog.csdn.net/bestsort/article/details/82947639

（代码参考于此，由于hdu2222有点卡时间，所以有所修改）

巴特西

字符串——AC自动机

一、前言

二、思路

三、代码

四、参考资料

最新文章

热门文章