over 2 years ago

这几天集中学习了一下,做一个小小的总结。
对于后缀自动机的学习,其实陈立杰的里讲得很清楚了,我讲的话估计也是民间算法,还不如不讲吧(其实是讲不清)。

inline void add(int x)
{
    Node *p = last;
    Node *np = newnode(p->l+1);
    while(p && !p->ne[x])
        p->ne[x] = np, p = p->fa;
    if(!p) np->fa = root;
    else
    {
        Node *q = p->ne[x];
        if(q->l == p->l+1) np->fa = q;
        else
        {
            Node *r = newnode(p->l+1);
            memcpy(r->ne, q->ne, sizeof r->ne);
            r->fa = q->fa, q->fa = np->fa = r;
            while(p && p->ne[x] == q)
                p->ne[x] = r, p = p->fa;
        }
    }
    last = np;
}

我们的其实是一个在线算法,就是每次加入一个节点来更新自动机。
后缀自动机有几个性质,好像陈立杰的论文里都讲了,我就不再讲了(其实是讲不清+1)。
那么我们来几道题吧。

spoj BEADS

就是求出一个串的最小表示法,把原串复制一遍建,再在自动机上从根节点沿着最小边走原串长度步即可。
beads.cpp

spoj NSUBSTR

给定一个字符串,输出长度为的出现次数最多的子串个数。
对该字符串建,求出拓扑序,计算出每个节点集合的大小来更新,再用来更新即可。
nsubstr.cpp

bzoj2555 SubString

给你一个字符串init,要求你支持两个操作
在当前字符串的后面插入一个字符串
询问字符串在当前字符串中出现了几次?(作为连续子串)
你必须在线支持这些操作。
其实这道题就是让我们动态维护后缀树,即可。(工业题啥的最讨厌了。。。)
SubString.cpp

spoj SUBLEX

就是给你一个求出第大的字符串(相同的字符串看做一个)。
这题就是很裸地直接在后缀树上计算即可。
sublex.cpp

spoj LCS

给你两个字符串要你求最长公共子串。
对于一个字符串建,另一个串在这上面跑,随时记录最大值即可。
lcs.cpp

spoj LCS2

给你个字符串,求出他们的最长公共子串。
对一个字符串建,记录其他每个串在每一个节点上匹配的最长长度,最后再遍历一遍自动机统计答案即可。
lcs2.cpp

ctsc2012 Cheat

题目颇长,自己看吧。
对于已有的串合起来建,相邻两个字符串之间多加一个'2',然后对于每一篇文章,求出每一个字符能往前最长匹配多少位,二分答案+单调队列优化即可。
Cheat.cpp
keep updating...

← 线性规划+floyd最小环(bzoj1027) bzoj1025:[SCOI2009]游戏 →
 
comments powered by Disqus