· 博主语文体育老师教的
· 本文年龄限定 16+
· 吐槽上面 2条的都是⑨
碰到AC自动机了...... (其实原题后缀数组靠谱一些> <)
虽然说写过 (一次) . 还是有(bu)记(ji)忆(dei) 的.
因为数据太水的原因导致完全大错特错的AC自动机AC了 ( 这就是传说中的Accept光环么 ? )
结果自己出数据就爆得成渣一样……
推荐论文:
1、《AC自动机基础入门》( 李翔 ) ( 我觉着看完就懂了……而且似乎没有那啥动态添加单词的AC自动机吧= =、)
AC自动机分为以下几个主体 :
字母树 (Trie)
这种大神不屑一顾的东西就不多讲了……反正就是节点重复利用什么的.
AC自动机施展的前提.
构造伪代码如下 :
Function trie(node now, char c)
If NOW->SON[c] = NULL //该节点不存在
now->son[c] = NewNode //新建一个节点
Return now->son[c]; //返回节点编号
End Function
Main ()
now = 0; //初始化节点
for i = 1 to len_s do
now = trie (now, s[i]) //找下一个节点
End Main
失败指针 (Failure)
假设你在一个由一些单词组成的字母树上做匹配, 沿着边走着走着突然发现走不了了 ( 要到达的节点不存在 ), 按照KMP的说法, 这时候应该找一个目前最长次匹配继续做.
如下图， a、b、c走不动后分别指向 c、d、d.
还不懂请看[1]……本博客专靠别人论文吃饭.
这种 "指向边” 称为 " 失败指针 “ (Failure)
接下来就是构造的问题咯……构造 节点 p 的失败指针的一般方法是 :
1、找到 p 的父亲的失败指针 fpr
2、if fpr -> son [wik [p]] != NULL then return fpr -> son [wik [p]] // wik [p] 表示 p 父亲的儿子 p 的编号
else fpr = fail [fpr] // 继续找直到找到 (肯定找得到.最坏的话会找到虚拟节点 0, 则failure指向根)
注意到上面的构造方法满足 : len [fail [p]] <= len [p] , 所以构造的时候从根节点开始BFS遍历节点.
并且, 需要设置虚拟节点 0, 0 的任意一个儿子均指向根. fail [root] = 0. 这个想想就明白了啦……> < (PS : 其实完全是不想写吧这种懒鬼! )
伪代码如下 ：
Proceduce ACrap()
ADD son of root INTO queue
while QUEUE IS NOT EMPTY
FIND failure of queue.head
ADD son of queue.head INTO queue
POP queue.head
End Proceduce
大概就这样了……诶?
不贴代码心里不舒服……虽然说不是正规的AC自动机.
题目呢……大概是给你一些单词, 每个单词有一个权值, 请你选出其中一些单词, 满足前一个单词是后一个单词的子串 (按照单词给出的顺序大小), 求最大权值和.
正解——后缀数组 + 线段树的复杂度很好证明, 但AC自动机的话似乎很容易卡啊……不过似乎卡了AC自动机的话正解也萎成渣了……
3.7补丁: 嗯...被屏屏哥D了.
AC自动机是不会被卡的……只要按Fail指针构树然后DFS序 + 线段树就可以了.
原来一直是想着沿着Fail指针裸找.
但自己稍微想了一下...实际上裸找的时间复杂度还是姑且能承受的吧……O(n√len) 稀里糊涂证明出来的……有待考证.
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
char s[300010];
int fail[300010], fap[300010];
int p[300010][27], t[300010];
int word_p[300010], word[300010];
int f[300010], mik[300010];
int test, poor, ans, ptans, now, sg, n;
int sta[20010], ent[20010], w[20010];
int q[300010];
int trie(int now, int c)
{
p[now][0] = 0; t[now] = poor; fail[now] = fap[now] = 0;
if (p[now][c] && t[p[now][c]] == poor) return p[now][c];
f[++sg] = now, mik[sg] = c; p[now][c] = sg;
for (int i = 0; i <= 26; ++i) p[sg][i] = 0;
return sg;
}
void acrap()
{
#define nowp q[head]
#define sec p[fpr][mik[nowp]]
int head = 1, tail = 0;
for (int i = 1; i <= 26; ++i)
if (p[1][i] && t[p[1][i]] == poor) q[++tail] = p[1][i];
fail[1] = 0;
for (; head <= tail; ++head)
{
int fpr = fail[f[nowp]];
while (!sec || t[sec] < poor) fpr = fail[fpr];
if (word[p[fpr][mik[nowp]]] == poor) { word[nowp] = poor;
if (word_p[p[fpr][mik[nowp]]] == poor) fap[nowp] = p[fpr][mik[nowp]];
else fap[nowp] = fap[p[fpr][mik[nowp]]];
}
else fap[nowp] = 0;
fail[nowp] = p[fpr][mik[nowp]];
if (word_p[nowp] == poor) word[nowp] = poor;
for (int i = 1; i <= 26; ++i) if (p[nowp][i] && t[p[nowp][i]] == poor) q[++tail] = p[nowp][i];
}
}
int main()
{
freopen("p3.in", "r", stdin);
freopen("p3.out", "w", stdout);
scanf("%d", &test); poor = sg = 1;
for (; test--; ++poor)
{
scanf("%d", &n); sta[0] = 1; f[1] = 0; mik[1] = 1; t[0] = t[1] = poor; sg = 1;
for (int i = 1; i <= 26; ++i) p[0][i] = 1, p[1][i] = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + sta[0]), scanf("%d", w + i);
sta[i] = sta[0]; ent[i] = sta[0] + strlen(s + sta[0]) - 1;
sta[0] = ent[i] + 1;
if (w[i] > 0) { now = 1;
for (int j = sta[i]; j <= ent[i]; ++j) now = trie(now, s[j] - 96);
word_p[now] = poor; t[now] = poor; fail[now] = fap[now] = 0;
}
}
acrap(); ptans = 0;
for (int i = 1; i <= n; ++i)
if (w[i] > 0)
{
now = 1; ans = 0;
for (int j = sta[i]; j <= ent[i]; ++j) {
now = p[now][s[j] - 96];
if (word_p[now] == poor) ans = max(ans, p[now][0]);
for (int map = fap[now]; map; map = fap[map]) ans = max(ans, p[map][0]);
}
w[i] = w[i] + ans; ptans = max(ptans, w[i]); p[now][0] = max(w[i], p[now][0]);
}
printf("%d\n", ptans);
}
}