AC自动机专题:多模式串匹配模板-HDU2896

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2896

重点理解两个数组:

$tran$数组就是一个有限状态机.$tran[i][j]$代表在节点$i$,遇到字母$j$所要跳转到的节点.

$fail$数组代表最长后缀状态。$fail[i]$代表节点i这个字符串最长相同后缀的状态所在的节点.他也是用来辅助求解$tran$数组的.

病毒传播

AC多模式串匹配模板题，没有什么好说的。贴个板子吧.

namespace AC{ int tr[maxn][130] , tot; int v[maxn] , fail[maxn]; void add (char * s , int g){ int u = 0; for (int i = 1 ; s[i] ; i++){ if (!tr[u][s[i]]) tr[u][s[i]] = ++tot; u = tr[u][s[i]]; } v[u] = g; } queue<int>q; void build (){ while (q.size()) q.pop(); for (int i = 0 ; i < 128 ; i++) if (tr[0][i]) q.push(tr[0][i]); while (q.size()){ int u = q.front();q.pop(); for (int i = 0 ; i < 128 ; i++){ if (tr[u][i]){ fail[tr[u][i]] = tr[fail[u]][i]; q.push(tr[u][i]); }else { tr[u][i] = tr[fail[u]][i]; } } } } void ask (char *t , vector<int> & res){ res.clear(); int u = 0; for (int i = 1 ; t[i] ; i++){ u = tr[u][t[i]]; // 转移 for (int j = u ; j ; j = fail[j]){ if (v[j] == 0) continue; res.push_back(v[j]); } } sort(res.begin(),res.end()); res.erase(unique(res.begin(),res.end()),res.end()); return ; } }