|Hdu 2222|AC自動機|Keywords Search

2019-11-11 03:23:31

字體：大中小

來源：轉載

供稿：網友

Hdu傳送門 AC自動機模板題，注意重復關鍵字的處理

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ms(i,j) memset(i,j, sizeof i); using namespace std;const int MAXN = 10000 + 5, _SIZE = 26; int n;struct acam{ int sz;//結點編號 int res; int ch[MAXN*51][_SIZE];//Tire int last[MAXN*51];//后綴鏈接 int f[MAXN*51];//失配函數 int val[MAXN*51][2];//結點的權值 bool used[MAXN*51];//用過 void init()//初始化 { ms(val,0); ms(ch,0); ms(used,false); sz = 1; res = 0; } void insert(char *s, int v)//插入一個模板 { int u = 0; int len = strlen(s); for (int i=0;i<len;i++) { int c = s[i] - 'a'; if (ch[u][c]) { u = ch[u][c]; } else { ch[u][c] = ++sz; u = ch[u][c]; } if (i==len-1) { val[u][0] = v; val[u][1]++; } } } void g(int j)//遞歸更新cnt { if (j&&!used[val[j][0]]) { res+=val[j][1]; used[val[j][0]] = true; g(last[j]); } } void find(char *T)//在T中匹配 { int len = strlen(T); int j = 0; for (int i=0;i<len;i++) { int c = T[i] - 'a'; j = ch[j][c]; if (val[j][0]) g(j); else if (last[j]) g(last[j]); } } void getFail()//獲得失配函數 { queue<int> q; f[0] = 0; for (int c=0;c<_SIZE;c++)//初始化進隊 { int u = ch[0][c]; if (u) { q.push(u); f[u] = 0; last[u] = 0; } } while (!q.empty()) { int r = q.front(); q.pop(); for (int c=0;c<_SIZE;c++) { int u = ch[r][c]; if (!u) { ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int j = f[r]; while (j&&!ch[j][c]) j = f[j]; f[u] = ch[j][c]; last[u] = (val[f[u]][0]) ? (f[u]) : (last[f[u]]); } } } }ac;char s[1000000 + 5];int main() { int kase; scanf("%d", &kase); while (kase--) { ac.init(); scanf("%d", &n); for (int i=1;i<=n;i++) { scanf("%s", s); ac.insert(s,i); } scanf("%s", s); ac.getFail(); ac.find(s);