LA 4670 AC自动机简单题
题意：给你n个子串（小写字母， n <= 150, len <= 70）,给你个文本串(len <= 10^6), 让你找到在文本串中出现次数最多的子串， 输出最多次数和子串。
注意：如果出现次数最多的有很多子串，要全部输出，还有n个子串会有重复。
做法：trie的每个节点用一个vector记录以该节点结尾的单词的标号，find()函数用数组cnt[]下标保存单词标号，值保存次数。然后扫描一下即可。
[cpp]
#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;
}
补充：软件开发 , C++ ,
