在同组的同学做情感分析相关算法的时候，他们应用到了多模匹配算法AC自动机，比单模匹配算法缩短了20倍，这里将AC自动机算法流程做一个记录。
#define M 57 #define N 1000007 using namespace std; struct node { node *fail node *next[26] int cnt void newnode() { fail = null; for (int i = 0; i < 26; i++) next = null; cnt = 0 } } class Ac_Automat { node *q[N], H[N], *root; int fr, tl, t; public: //初始化 void init() { fr = tl = 0; t = 0; H[t].newnode(); root = &H[t++]; } //插入节点 void insert(char *s) { int i, k, len; len = strlen(s); node *p = root; for(int i = 0; i < len; i++) { k = s[i] - a; if(p -> next[k] == null) { H[t].newnode(); p->next = &H[t++]; } p = p->next[k] } p->cnt++; } //建立失败节点 void build() { root->fail = null; q[tl] = root; while (fr <= tl) { node *tmp = q[fr++]; node *p = null; for (int i = 0; i < 26; i++) { if (tmp->next[i]) { if (tmp == root) { tmp->next[i]->fail = root; } else { p = tmp->fail; while (p!=null) { if (p->next[i]) { tmp->next[i]->fail = p->next[i]; break; } p = p->fail; } if (p == null) temp->next[i]->fail = root; } q[++tl] == temp->next[i]; } } } } //查找字符串 int query(char *s) { int res = 0; node *p = root; int len = strlen(s); for (int i = 0; i < len; i ++) { int k = s[i] - ['a']; //匹配不到，跳转到对应字母的失败节点继续匹配。 while (p->next[i] == null && p != root) { p = p->fail; } //匹配当前字母成功，指针移向next节点，为下一个字母匹配做准备。 p = p->next[k]; //next节点为空，下一个字母从root开始匹配。 if (p == null) p = root; node *tmp = p; //计算当前匹配跳过了多少节点。 while (tmp != root && tmp->cnt != -1) { res += tmp->cnt; tmp -> cnt = -1; tmp = tmp->fail; } } return res; } }