搞了几天sam,虽说不是很能理解,不过总结什么的还是得写写的。。。

首先,还是推荐几篇论文吧。。

  1. clj的论文 《陈立杰营员交流资料.pptx》(大力推荐)
  2. http://cxjyxx.me/?p=244http://cxjyxx.me/?p=246
  3. http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

后缀自动机如何构建这里就不讲了。。详细见上述论文
这里只介绍下性质和应用。
当然如果上面的论文没看懂也是可以看看本弱的理解的。。。

为了方便讲述,我先贴一下我的模板吧(其实跟clj的基本一样,就是变量名换一下,然后改成用数组模拟指针罢了)

void add(int c)
{
    int np = ++cnt,p = last; last = np;
    l[np] = ++len; //memset(ch[np],0,sizeof ch[np]);
 lp[np] = 0;//我自己加的东西
 for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) fa[np] = 1;
    else {
        int q = ch[p][c];
        if (l[p] + 1 == l[q]) fa[np] = q;
        else {
            int nq = ++cnt;
            lp[nq] = lp[q] + l[q] - 1 - l[p];//我自己加的东西
         l[nq] = l[p] + 1; memcpy(ch[nq],ch[q],sizeof ch[q]);
            fa[nq] = fa[q];
            fa[q] = fa[np] = nq;
            for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
        }
    }
}

可以看到我的sam的每个结点有l,lp,fa,ch[26]四个属性。lp是我自己加上去的,是为了构造后缀树和后缀数组的。
其中l就是clj课件里面的Max,fa就是fail指针,也是后缀树上的父亲,ch[26]是自动机上的转移。
下面就来详细介绍下这几个变量的定义和性质吧。

定义和性质

  1. 后缀自动机是个自动机,能够接受所有后缀(接受点就是last和其fail指针一直到root的链上的点)。
  2. 自动机上每个点都是一个状态,代表了一个字符串集合S,其中每个字符串都是原串的子串,而且出现位置的右端点集合(right集合)都是一样的。

    例如原串是ABBABBABBBBBABBA
    BBABBABBBBBABBA
    BBABBBBBABBA
    BBABBA
    BBA
    此时S集合就是
    由此可以推出一个性质,就是S集合里面的字符串长度是递增的,并且小串都是大串的后缀。
    对于点p,我们不妨记长度区间为[Min(p),Max(p)]。
    在我的代码中,l[p]就是Max(p)。上述例子中l[p]就是3。为了方便描述,我们定义S(p)是p的代表串集合。

  3. 对于一个点p,fa[p]代表的意思就是|right|最小的且right(q)包含right(p)的q。
    可以发现S(q)肯定都是S(p)的后缀,而且Min(p) == Max(q) + 1。由此可以推出|S(p)|。

  4. ch[p]就是自动机上面的转移。而且如果q可以由p转移到,那么Max(q)>Max(p) 而且 Min(q)<=Min(p)+1(后面那个是我自己yy的,不知道有没有错。。。有问题的话欢迎留言)

  5. 说说lp[p]吧。注意到我们建自动机的时候都只记了长度l,那如果我们想要输出p的代表串S集合呢?
    可以记一个lp[p],代表S(p)中最长串在原串中的任意一个出现位置的左端点。
    新建一个前缀时,lp[p]=0,
    如果新建一个nq用替代原来的点q时,lp[nq] = lp[q] + l[q] - 1 - l[p];(详见代码)

好像bala了一大堆。。。

没办法。。。

谁叫我语文渣呢?

应用

应用的话我们按自动机和后缀树来分。

  1. 后缀自动机:
    众所周知,从起点走到每个点的每条路经都是一个子串,而且两两不同。
    我们只要按字典序遍历边就能够从小到大遍历子串了。
    然后我们可以处理出每个点往下走能走到几个子串。
    这样还可以做第K大子串什么的。

    还有一个应用,就是串的匹配。
    对于A串建自动机,对于B串在A串上匹配,能够得出以B串中每个点为右端点,左端点能够匹配到多长。
    代码大概长这样:

        for (int p = 1,len = 0; *s; ++s) {
            int c = *s - 'a';
            while (p && !ch[p][c]) p = fa[p];
            if (!p) p = 1,len = 0;
            else {
                len = std::min(l[p],len) + 1;
                p = ch[p][c];
            }
        }
    

    其中len就是匹配的长度。
    这个还是很有用的。配合上后缀树和dp就能够搞出奇奇怪怪的题。
    (例如BZOJ 2806: [CTSC2012 Day2 T1]熟悉的文章(cheat))

  2. (逆串)后缀树(也是fail树):
    对于一个串,如果要求他的出现次数的话,就是他所对应的节点的|right|大小。
    这个可以用dp,在fail树上dp。先把每个右端点的最底层的贡献+1(其实就是每个前缀结点),然后按Max基数排序,倒着更新上去就完了。

    后缀树上除了叶子以外,|right(p)|>=2,叶子的|right(p)|==1。

    每个叶子对应一个前缀,但是每个前缀不都是叶子。

然后。。贴点题目吧。。


POJ-1509 Glass Beads

题意:求一个字符串的最小表示的开始下标。
也就是给一个字符串S,每次可以将它的第一个字符移到最后面,求这样能得到的字典序最小的字符串。

首先把原串copy一遍
直接从root开始往按字典序遍历边走len步就完了。

代码?没打


SPOJ NSUBSTR
给一个字符串S,令F(x)表示S的所有长度为x的子串中,出现次数的最大值。求F(1)..F(Length(S))

求出每个点的|right|,然后这个点可以对f(l(fa(p))+1...l(p))贡献|right|的答案。
可以用线段树,不过其实直接标记最长串,最后倒着扫就完了。

代码


BZOJ2555 SubString
给你一个字符串init,要求你支持两个操作
(1):在当前字符串的后面插入一个字符串
(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)
你必须在线支持这些操作。

这题就是裸的lct + sam
代码


SPOJ SUBLEX
给一个长度不超过90000的串S,每次询问它的所有不同子串中,字典序第K小的,询问不超过500个。

dp处理出每个点往下走能够走出多少个串。
f[i]=sigma(f[ch[i][c])+1
这个可以按Max排序之后倒着推就好了。
询问的时候看一下走下去个数是否<=k,是的话就走下去,然后--k;否则就找下一条边。
代码


SPOJ LCS
给定两个长度不超过250000的串,求它们的最长公共子串。

用一个串建sam,另一个串在上面跑。这样就可以得出第二个串的每个位置最多能够匹配多少。最后取一个max就好了。
代码


SPOJ LCS2
给定最多10个串,求lcs

思路和上一题差不多,就是用一个串建sam,然后用另外几个去跑,对于sam上的每一个状态都记录一个len。len[i]对于同一个串取max,对于不同串取min。
代码


BZOJ 2806: [CTSC2012 Day2 T1]熟悉的文章(cheat)
题目大意自己去看吧。。反正是中文的。

首先把标准作文库用2连起来,建sam。
然后对于一篇文章,二分L,用dp判定。
预处理出a[i]代表i这个位置能够匹配多长。
f[i]代表前i个位置最多能匹配多长。f[i]=Max(f[j]+i-j){0<=j<=i-a[i]}
很容易发现这个dp可以用单调队列优化。
然后就可以过了。

代码


codeforces 235C - Cyclical Quest
题目大意:给一个字符串S,再给一个字符串T,设T的长度为len,问T的循环串在S中出现的次数,这里循环串的定义是:对于一个长度为len的字符串,我们把它首尾相接,然后从任意位置开始走len步所得到的串我们叫做T的循环串。如abaa的循环串有 abaa,baaa,aaab,aaba。(注意如果重复只算一次。比如aaa的循环串只有一个aaa)

题解


hdu4641 k-string
题目大意:给一个长度为n的字符串S,定义k-string为在字符串S中出现次数大于等于k次的子串,也就是存在至少k对(i,j)使得0 <= i <= j < n且Si,Si+1…Sj构成的子串与该k-string相同。现给一个初始字符串,然后执行m个操作,每个操作有两种:1.往当前字符串S末尾添加一个字符; 2.询问当前不同的k-string有多少种。

题解


好累啊。。。
不知道有没有人看懂。。。。
算了,我看得懂就好~~~~~

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project