AC自动机详解

2022-03-24 04:42| 来源: 网络整理| 查看: 265

第一步：构建Trie树

和普通的trie树构建方法一样如：依次插入字符串apple、aply、cold、cool、cook 在这里插入图片描述

struct node { int fail;//失配指针 int son[26];//儿子节点 int end_num;//结尾标记 }trie[N]; int pos;//tire的指针 void build_trie(string s) {//建立字典树 int now = 0; for (int i = 0; i //构建fail指针 queue q; for (int i = 0; i trie[t].fail = 0; q.push(t); } } while (!q.empty()) { int u = q.front(); q.pop();//取出节点u for (int i = 0; i //如果子节点v存在的话 //子节点v的fail指针指向当前节点的fail指针所指向的节点的相同子节点(默认为0即跟根节点) trie[v].fail = trie[ptr_fail].son[i]; q.push(v); } //否则当前这个儿子v指向当前节点fail指针所指向的节点的相同子节点(默认为0即跟根节点) else trie[u].son[i] = trie[ptr_fail].son[i]; } } } 第三步：模式匹配

匹配的核心是从目标串从头逐个开始，在ac自动机中进行匹配，匹配上的则计数，若未匹配上则跳转失配位置进行尝试匹配，直到全部匹配完成

int query(string s) { int ans = 0; int now = 0; for (int i = 0; i ans += trie[j].end_num; trie[j].end_num = -1;//标记已统计过 } } return ans; }

P3808 【模板】AC自动机（简单版）

#include #include using namespace std; template void debug(Args... args) {//Parameter pack auto tmp = { (cout //建立字典树 int now = 0; for (int i = 0; i //构建fail指针 queue q; for (int i = 0; i trie[t].fail = 0; q.push(t); } } while (!q.empty()) { int u = q.front(); q.pop();//取出当前节点u for (int i = 0; i //如果子节点v存在的话 //子节点v的fail指针指向当前节点的fail指针所指向的节点的相同子节点(默认为0即跟根节点) trie[v].fail = trie[ptr_fail].son[i]; q.push(v); } //否则当前这个儿子v指向当前节点fail指针所指向的节点的相同子节点(默认为0即跟根节点) else trie[u].son[i] = trie[ptr_fail].son[i]; } } } int query(string s) { int ans = 0; int now = 0; for (int i = 0; i ans += trie[j].end_num; trie[j].end_num = -1;//标记已统计过 } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; string temp; for (int i = 0; i

【本文地址】

AC自动机详解

AC自动机详解

今日新闻

推荐新闻