题意:给你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]);