-
稳定on不再玄学的AC自动机之fail树
-
子串是否在母串中出现过
-
最板子的板子,构建AC自动机,正经的AC自动机失配之后会回到自己父亲后缀的最长前缀
-
也就是ne指针指的位置,有时候也叫做fail指针,但是这种会多走好多步详见
-
这位大佬的造的特例link
-
所以一个优化是Trie图我们直接跳到有我这个儿子的父亲的fail指针位置不就好了吗
-
于是Trie图就这样被发掘成为AC自动机的小优化
-
但是我们发现,这种做法依旧是n^2的,因为找到匹配位置向上回溯的时候最坏是on的
-
也许可以使用vis数组判断当前的位置有没有被用过,但是仅适用于部分题
-
于是我们观察了ne指针的性质发现他一定是一颗树,我们构建出来这棵树叫做fail树
-
当前所有向上回溯的fail都可以利用树上差分单点加来实现,最后一遍前缀和就行
-
子串在母串中最大出现次数
build();
scanf("%s", str);
int res = 0;
for(int i = 0, j = 0; str[i]; i ++) {
j = tr[j][str[i] - 'a'];
siz[j] ++;
}
for(int i = 1; i <= idx; i ++) add(ne[i], i);
dfs(0);
for(int i = 1; i <= n; i ++) {
res += !!siz[id[i]];
}
pf(res, 1);
for(int i = 0, j = 0; i < str.size(); i ++) {
j = tr[j][str[i] - 'a'];
siz[j] ++;
}
memset(h, -1, sizeof h);
for(int i = 1; i <= idx; i ++) {
add(ne[i], i);
}
dfs(0);
int mx = 0;
vector<string> ans;
for(int i = 1; i <= n; i ++) {
if(siz[id[i]] > mx) {
mx = siz[id[i]];
ans.clear();
ans.push_back(ss[i]);
}
else if(siz[id[i]] == mx) {
ans.push_back(ss[i]);
}
}
pf(mx, 1);
for(int i = 0; i <= n; i ++) {
for(int j = 0; j < ans.size(); j ++) {
if(ans[j] == ss[i]) {
cout << ans[j] << endl;
break;
}
}
}
void insert(int i)
{
int p = 0;
for(int i =0;str[i];i++)
{
int t = str[i]-'a';
if(!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
}
cnt[p] ++;
id[i] = p;
}
build();
scanf("%s", str);
int res = 0;
for(int i = 0, j = 0; str[i]; i ++) {
j = tr[j][str[i] - 'a'];
siz[j] ++;
}
memset(h, -1, sizeof h);
for(int i = 1; i <= idx; i ++) {
add(ne[i], i);
}
dfs(0);
for(int i = 1; i <= n; i ++) pf(siz[id[i]], 1);