写这篇文章的原因时队友Sagitta同学在某日问他的某段代码为何得到WA,分析之后发现是这个问题。

在AC自动机的字符串匹配过程当中,我们注意到它的query之类的函数往往是这样写的:

int query(char *str)
{
    int now = root;
    int ret = 0;
    for (; *str; str++)
    {
        now = next[now][*str];
        int temp = now;
        while (temp != root)
        {
            ret += flag[temp];
            temp = fail[temp];
        }
    }
    return ret;
}

有人?认为,fail指针只用于失配时的处理,如果预处理了失配的情况,就不需要管fail指针了,然而事情并非总是如此,不妨回忆一下fail指针(当然也包括KMP的next数组)的定义“当前字符串的最长不失配的后缀”(差不多是这个意思,理解一下就好)

根据上面这个的定义,我们会发现,fail指针实际上也包含了另外一层意思,考虑我们在KMP的next数组的行为,不难发现,KMP高效的原因其实是因为我们将从多个地方开始的字符串匹配同时处理了。考虑aaaaaaab这样的字符串,当我们跟着next数组跳动的时候,其实就是放弃了从某个位置开始的一个子串(因为它不会成为最终的匹配)又由于我们fail数组的性质,当我们走到第7个a的时候,我们其实可以通过next数组走到第6个、第5个……第一个a上,这正是相当于我们同时有7个起点在进行匹配的尝试。而AC自动机上的fail指针起着同样的作用。

那么,这就说明,fail指针不能被忽略,而在字符串匹配的过程当中,我们会利用匹配的过程穿插标记的收集工作,那么在使用AC自动机解决动态规划的问题的时候呢?

可以发现,在利用AC自动机解决动态规划的过程当中,我们需要提前处理好标记的问题(你看,标记的收集可能是O(n)的呢!)而这个标记收集的位置就是在建自动机的函数里,而且只需要一句话:

flag[x] += flag[fail[x]]

这里的加法显然是广义的加法,视情况换成或或者其它的什么东西。