LA 4670 AC自动机简单题
题目链接
题意：给你n个子串（小写字母， n <= 150, len <= 70）,给你个文本串(len <= 10^6), 让你找到在文本串中出现次数最多的子串， 输出最多次数和子串。
注意：如果出现次数最多的有很多子串，要全部输出，还有n个子串会有重复。
做法：trie的每个节点用一个vector记录以该节点结尾的单词的标号，find()函数用数组cnt[]下标保存单词标号，值保存次数。然后扫描一下即可。
#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <algorithm>using namespace std;const int maxn = 10004 * 51;int n;char s[1000006], str[155][77];int cnt[155];struct AC { int c[maxn][26], tot, f[maxn];vector <int> id[maxn]; int idx(char c) { return c-'a'; } int new_node() { memset(c[tot], 0, sizeof(c[tot])); id[tot].clear(); return tot++; } void init() { tot = 0; new_node(); } void insert(char *s, int pos) { int i, j, u = 0, n = strlen(s); for(i = 0; i < n; i++) { int k = idx(s[i]); if(!c[u][k]) c[u][k] = new_node(); u = c[u][k]; } id[u].push_back(pos); } void getfail() { int i, j, u, v; queue <int> q; f[0] = 0; for(i = 0; i < 26; i++) { u = c[0][i]; if(u) { f[u] = 0; q.push(u); } } while(!q.empty()) { u = q.front(); q.pop(); for(i = 0; i < 26; i++) { v = c[u][i]; if(!v) { c[u][i] = c[f[u]][i]; continue; } // 这行是AC自动机改造： 没改造的是这样的 if(!v) continue; j = f[u]; while(j && !c[j][i]) j = f[j]; f[v] = c[j][i]; q.push(v); } } } void find(char *s) { int i, j, u = 0, n = strlen(s); for(i = 0; i < n; i++) { int k = idx(s[i]);//while(u && !c[u][k]) u = f[u]; // 改造后的AC自动机，这句话不用写 u = c[u][k]; for(j = u; j; j = f[j]) { for(int k = 0; k < id[j].size(); k++)cnt[id[j][k]]++; } } }}ac;int main() { int i, j; while( ~scanf("%d", &n) && n) { ac.init();memset(cnt, 0, sizeof(cnt)); for(i = 1; i <= n; i++) { scanf("%s", str[i]); ac.insert(str[i], i); } ac.getfail(); scanf("%s", s); ac.find(s);int ans = 0;for(i = 1; i <= n; i++)if(ans < cnt[i]) ans = cnt[i];printf("%d\n", ans);for(i = 1; i <= n; i++)if(ans == cnt[i]) puts(str[i]); } return 0;}