AC自动机算法算是比较简单直观的字符串匹配自动机，它其实就是在一颗Trie树上建一些失配指针，当失配时只要顺着失配指针走，就能避免一些重复的计算。比如对于字符串antibody和tide，如果第一个串匹配到第5个字符（b）失配了可以直接走入第二个串的第3个字符（d）进行匹配，因为前面的“ti”是公共的，如果能匹配到第一个串的第5个字符，那么前面两个肯定是ti。[ Aho-Corasick自动机浅析 AC自动机算法详解
#include <bits/stdc++.h> using namespace std; const int MAXN = 1E5, MAXC = 26; struct node { node * fail; node * nxt[26]; int id; node() { fail = nullptr; fill(nxt, nxt+MAXC, nullptr); id = -1; } }; char keyword[100], s[MAXN]; void insert(const char *s, int id, node *root) { node *p = root; for(int i=0; s[i]!='\0'; ++i) { if(p->nxt[s[i]-'a'] == nullptr) p->nxt[s[i]-'a'] = new node; p = p->nxt[s[i]-'a']; } p->id = id; } void build_fail_point(node * root) { root->fail = nullptr; queue<node*> que; que.push(root); while(!que.empty()) { node * now = que.front(); que.pop(); node * p = nullptr; for(int i=0; i<MAXC; ++i) { if(now->nxt[i] == nullptr) continue; if(now == root) now->nxt[i]->fail = root;//root所有子节点fail指向root else { p = now->fail; while(p != nullptr)//沿着失败指针往上走 { if(p->nxt[i] != nullptr)//直到找到一个存在s[i]子节点的节点 { now->nxt[i]->fail = p->nxt[i];//失败指针指向该子节点 break; } p = p->fail; } if(p == nullptr) now->nxt[i]->fail = root;//没有找到, fail指向root } que.push(now->nxt[i]); } } } vector<pair<int, int>> query(const char *s, node *root) { vector<pair<int, int>> ret; int len = strlen(s); node * p = root; for(int i=0; i<len; ++i) { int index = s[i] - 'a'; while(p->nxt[index] == nullptr && p!=root) p = p->fail;//如果这个字母没有匹配, 沿着失败指针走, //直到匹配或者到root if(p->nxt[index] == nullptr) continue;//没有匹配 p = p->nxt[index]; node * t = p; while(t!=root)//匹配, 沿着这个节点的失败指针, 找到所有以s[i]结尾的节点 { if(t->id != -1) ret.push_back(make_pair(t->id, i)); t = t->fail; } } return ret; } void del(node * root) { for(int i=0; i<MAXC; ++i) if(root->nxt[i] != nullptr) del(root->nxt[i]); delete root; } int main() { node * root = new node; int id = 0; while(cin >> keyword && keyword[0]!='#') insert(keyword, id++, root); build_fail_point(root); cout << " s " << endl; cin >> s; vector<pair<int, int>> v = query(s, root); for(auto x : v) cout << x.first << " " << x.second << endl; return 0; }