本文主要是介绍码题集-AC自动机（模板），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
AC自动机：
（1）一个长串，多个短串，求长串中匹配了几个短串（包括分别匹配了几个，总共匹配了几类）
（2）此处模板为长串中匹配了几个短串；
（3）复杂度为O（n);
（4）理论基础
- Trie树
- KMP
- 链表
思路：
（1）问题分析：给定1e6模式长串，多个短串，求其中匹配的各模式串中个数最大者及其个数；
（2）分析：多模式串匹配问题，考虑AC自动机；
（3）过程：
- 建立string数组与int数组统计短串及其个数；
- 先建立短串与标记的map映射；
- 对于多个子串，建立Trie树，并将短串在Trie树中的终点映射到短串标记；
- 建立链式关系；
- 查询时查到后对该节点对应短串进行计数；
- 找到最大出现次数及其节点；
代码：
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int maxn = 2*1e6+9;int trie[maxn][26]; //字典树
int cntword[maxn]; //记录该单词出现次数
int fail[maxn]; //失败时的回溯指针
int cnt = 0;
int n;
string s;
map<string,int> qq;
map<int,int> node_i;
int ccnt[50];
string ss[50];void insertWords(string s)
{int root = 0;for(int i=0;i<s.size();i++){int next = s[i] - 'a';if(!trie[root][next])trie[root][next] = ++cnt;root = trie[root][next];}cntword[root]++; //当前节点单词数+1int s_n = qq[s];node_i[root] = s_n;
}
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];}}
}void query(string s)
{int now = 0,ans = 0;for(int i=0;i<s.size();i++){ //遍历文本串now = trie[now][s[i]-'a']; //从s[i]点开始寻找for(int j=now;j && cntword[j]!=-1;j=fail[j]){//一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).ans += cntword[j];if(cntword[j] > 0){int t = node_i[j];ccnt[t] += 1; }}}
}void solve()
{cnt = 0;memset(trie,0,sizeof trie);memset(cntword,0,sizeof cntword);memset(fail,0,sizeof fail);memset(ccnt,0,sizeof ccnt);node_i.clear();qq.clear();for(int i=0;i<n;i++){cin >> s ;qq[s] = i;ss[i] = s; insertWords(s);}fail[0] = 0;getFail();cin >> s ;query(s);int maxn = 0;for(int i = 0;i < n;i ++){maxn = max(maxn,ccnt[i]);}cout << maxn << endl;for(int i = 0;i < n;i ++){if(ccnt[i] == maxn){cout << ss[i] << endl;}}} int main()
{while(cin >> n,n != 0){solve(); } return 0;
}这篇关于码题集-AC自动机（模板）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
