后缀系列数据结构

Last updated on: 2018.1.8

okay,今天我们来认识新的大家庭那就是后缀大家庭。

在这之前我先说几句话。

[0x00 和正文毫无关联的前言]

事情是这样的,风和日丽的一天,pkl点开了一个网页,看到了一个短语:

IMG_4870

......

....

.........

IMG_4870

IMG_4860

and

1B40CC1DB4558CA17DAEA9D637A7663F

DE914711D5F04A3B520544065E182D80

于是我迫不及待地想要写一篇关于后缀系列的东西。

以下是正文,还有真正的标题。

代码放上来实在是太占地方了。。。就不从OJ上搬过来了

[0x01 后缀三姐妹·后缀数组]

我还不会dc3QAQ

不用指望这里会有什么讲解了...

后缀数组,就是把后缀排好序了的数组。

由于是对后缀排序,所以可以用到一些后缀的一些性质进行排序。由于字符集的缘故我们可以桶排,使其转化成基数排序。(离散化之后字符集会相对变小一些)

每次排序,有了第一关键字我们可以轻易得到第二关键字的排序结果,而有了这两个我们又可以很容易地合成下一次排序的第一关键字。

这样我们的复杂度是$O(len \log len)$的

小试牛刀

  1. 求一个串有多少个本质不同的子串

  2. 求一个串有多少个本质不同的至少包含一个'v'字符的子串

    预处理某位置之后第一个v出现的位置,之后参考T1

  3. 求一个串有多少个本质不同的子串,使得这个子串中模式串T出现过

    参考T2

一些题目

BZOJ 4698 SDOI2008 Sandy的卡片

有一些由数字组成的串。 定义两个串的子串相同:两个串的子串长度相同并且一个子串的所有数都加上一个数与另一个串恰好完全相同。 求所有串的最长的相同子串。

本题难点在看出差分和一些细节的处理。

把所有的字符串接起来(中间增加辨识符)建立SA

之后二分贪心判定就可以了。

BZOJ 4516 SDOI2016 生成魔咒

每次在串首加入一个字符并询问此时整个串本质不同的子串数量。

考虑如何计算加入一个后缀带来的贡献,需要知道它在SA的前驱和后继

那么离线下来,最后用set维护就好了。

Upd on 2018/1/9:

现在我们来想想SAM的做法。

BZOJ 4310 跳蚤

将一个字符串分成不超过K段,使得这K段中,所有子串中字典序最大的最小。即每一段当中取一个最大的子串,再在所有段的最大子串再取一个最大值,让这个最大值最小。长度10W。

明显的思路是二分是第几个本质不同的子串(即二分字典序)

每一段中一定是选某个后缀最优,所以判定的时候倒着贪心分段就行了。

调试过程中遇到的问题居然是rmq。。。其次的问题是,注意询问lcq的区间要++ l

BZOJ 2865 && 1396 字符串识别

双倍经验权限题(两道都是权限题)。。。

给定一个字符串S,与一个整数K,定义S的子串T=S(i, j)是关于第K位的识别子串,i≤K≤j、子串T只在S中出现过一次。给定S,XX希望知道对于S的每一位,最短的识别子串长度是多少。

如果直接考虑每次统计点x的答案的话不太好统计,考虑每一个子串对答案的贡献就行了。

但发现维护的区间其中一个是一个公差为1的等差数列。但实际上没有必要用李超线段树这么麻烦,由于那部分的贡献是n-i+1,那么可以直接用线段树维护了。

BZOJ 4556 TJOI2016&&HEOI2016 字符串

给定一个串s和参数abcd,问s[a,b]内的子串和s[c,d]之间的lcp最大值是多少。

哇。。。

这个题想了一会之后卡在不知道如何处理$\max _{i\in [a,b]}(lcp(suffix_i,suffix_c), b-i+1) $这个地方了。。。

看了看网上的题解说还有SAM做法,先马下来。

这个事情告诉我们lcp长度满足二分性质常常会利用到二分的技巧这个玩意要好好利用。。

考虑二分lcp长度,当答案为l时,$i\in[a,b - l + 1]$

同时要满足和cd串有大于等于l的lcp的后缀。

这个怎么办呢。首先只有sa中位置越靠近rk[i]的后缀才会和它有更大的lcp,那么可以二分出这个块边界。

之后只要在这个块里有$sa[i]\in [a,b - l + 1]$ 就满足需求,主席树就行了。

总复杂度log方的。

这破题我居然写了这么多行。。。。

回去还要补一个叫优秀的拆分的题。。

Upd on 12.26:

BZOJ 4650 NOI2016 优秀的拆分

通过暴力的启示我们发现我们在求这样一个式子$\sum f_ig_{i+1}$

正着直接统计不好统计,考虑对于每一个可能的模式串A情况计算它的贡献去更新fg数组。

更严峻的问题是如何找到每一个可能的模式串A。。

题解给出了一个十分巧妙的方法。

如果我们知道了AA中A的长度,将整个序列分为$\lceil \frac{n}{l_A} \rceil$段,对于每一个可能的AA,一定会穿过中间的相邻某两个点。那么不正好卡在这两个点上的串怎么统计呢,画一画,考虑它偏移成了什么样子,发现实际上求出这两个相邻的点分别的前缀后缀之间的lcs和lcp,然后把他们接起来如果大于$l_A$那么就有贡献产生了,这样有贡献的左端点和右端点的范围就都知道了,每次
对这两个区间分别贡献1,由于只询问一次,树状数组维护一个差分就行了。

UPD on 3.5

树上SA

离线

今天学习了如何在trie上建立SA。。。也就是树上的SA。。。
我们考虑利用倍增的方法。
建SA的时候我们预处理出点向上l的点是谁,然后就可以愉快地求出下第一关键字何第二关键字进行排序了。
然后我们遇到了一个问题就是如何求height。考虑倍增,我们记录下每一层的第一关键字排序结果,由于我们是离散化好了的,所以判断rk是否相等就可以判断后缀是否相等了。
然后判断lcp就可以通过路径最小值求得了,这个我们可以倍增+rmq。
不要忘了在uv本来就相等的时候加上dep

资料
例题

pyz的代码:

inline void build_anc()
{
    log_tab[0] = -1;
    for (int i = 1; i <= n; ++i)
        log_tab[i] = log_tab[i >> 1] + 1;
 
    for (int u = 1; u <= n; ++u)
        dep_l[u] = log_tab[dep[u]];
 
    for (int l = 0; l < log_tab[n]; ++l)
        for (int u = 1; u <= n; ++u)
            anc[l + 1][u] = anc[l][anc[l][u]];
}
 
int sa[MaxN], rank[MaxN];
int tab[MaxLogN][MaxN];
 
int height[MaxN];
int st[MaxLogN][MaxN];
 
int w[MaxN];
 
inline bool sa_init_equal(int *x, int l, int u, int v)
{
    return x[u] == x[v] && x[anc[l][u]] == x[anc[l][v]];
}
 
inline void sa_init()
{
    int *x = rank, *y = height;
    int m = 26;
    fill(w, w + m + 1, 0);
    for (int i = 1; i <= n; ++i)
        ++w[x[i] = tab[0][i] = ancw[i]];
    for (int i = 1; i <= m; ++i)
        w[i] += w[i - 1];
    for (int i = n; i >= 1; --i)
        sa[w[x[i]]--] = i;
 
    int k = *max_element(dep_l + 1, dep_l + n + 1);
    for (int l = 0; l <= k; ++l, swap(x, y))
    {
        fill(w, w + m + 1, 0);
        for (int i = 1; i <= n; ++i)
            ++w[x[anc[l][i]]];
        for (int i = 1; i <= m; ++i)
            w[i] += w[i - 1];
        for (int i = 1; i <= n; ++i)
            y[w[x[anc[l][i]]]--] = i;
 
        fill(w, w + m + 1, 0);
        for (int i = 1; i <= n; ++i)
            ++w[x[i]];
        for (int i = 1; i <= m; ++i)
            w[i] += w[i - 1];
        for (int i = n; i >= 1; --i)
            sa[w[x[y[i]]]--] = y[i];
 
        y[0] = 0, y[sa[1]] = m = 1;
        for (int i = 2; i <= n; ++i)
        {
            m += !sa_init_equal(x, l, sa[i], sa[i - 1]);
            y[sa[i]] = m;
        }
 
        for (int i = 1; i <= n; ++i)
            tab[l + 1][i] = y[i];
    }
    for (int i = 1; i <= n; ++i)
        rank[sa[i]] = i;
 
    for (int i = 2; i <= n; ++i)
    {
        height[i] = 0;
        int u = sa[i], v = sa[i - 1];
        int up = min(dep_l[u], dep_l[v]);
        for (int l = up; l >= 0 && u != v; --l)
            if (tab[l][u] == tab[l][v] && anc[l][u] && anc[l][v])
            {
                height[i] |= 1 << l;
                u = anc[l][u];
                v = anc[l][v];
            }
        if (u == v)
            height[i] += dep[u];
    }
 
    for (int i = 2; i <= n; ++i)
        st[0][i] = height[i];
    for (int l = 0; l < log_tab[n]; ++l)
        for (int i = 2; i + (1 << l + 1) - 1 <= n; ++i)
            st[l + 1][i] = min(st[l][i], st[l][i + (1 << l)]);
}
 
inline int get_lcp(int a, int b)
{
    if (a == b)
        return dep[sa[a]];
    if (a > b)
        swap(a, b);
    int l = log_tab[b - a++];
    return min(st[l][a], st[l][b - (1 << l) + 1]);
}

UPD on 3.14

在线

...是个暴力log方的。
在线的可以考虑在树上倍增哈希来比大小,然后直接sort,求height就直接倍哈希求lcp。

[0x02 后缀三姐妹·后缀自动姬]

今天我们来认识后缀大家族的又一名成员:后缀自动姬,又称SAM(Suffix Automaton)

先扯一会儿淡

在这里我要介绍的是一种“后缀树向的”SAM,并不是CLJ在ppt里讲的那种讲解思路,感觉这个角度切入SAM十分地简单易懂。

emmmmm这就导致一个问题,我发现这个方法确实和网上我看到的主流讲SAM讲得角度切入不太一样。。所以他们说的很多概念我都不知道是啥(回头可以看看)

FSF的课件在 这里

先简单地说一说后缀树。顾名思义,后缀树就是一棵能表示所有后缀的树,现在我们先来考虑一个暴力,把所有后缀一个一个插入到trie中,不做任何处理,这样的话空间复杂度比较容易GG的,我们把它优化一下,建一个类似虚树的东西,把无用的非关键点merge成一整条边,例如S=aabdabd时,树长成这个德行:

TIM截图20171228142846

这样的话就可以保证点数是O(n)的了,可以从虚树的角度理解,我们一共有n个关键点,稍微仔细想想这个玩意儿点数肯定是O(n),具体来说点数在2n左右。其实还有另外一种解释方法,等我后面说完了再说。

考虑每次在串S的结尾加入一个字符,我们如何维护这么一棵后缀树呢?

串尾加入对于每一个后缀都有修改,这很不好办,但是串首就不一样了,只是新增了一各后缀而已,所以我们把整个串倒过来维护前缀就行了。

接下来开始讲正事儿

一般说正事儿的时候我就不敢保证正确性了因为我口胡了一大堆东西,如果你们看出了有什么bug请立刻联系我,谢谢,你的举动可能就会拯救一个脑残边缘的无知少女

我们维护一个trans[x][c]表示x节点表示的字符串/在串首加入c字符后(称这个串为S')/的深度最浅的/满足S'是它的前缀的节点编号是什么。

为了方便食用我先扔一个图

TIM截图20171228153454

这个玩意儿我们怎么维护呢,由于我们是按照顺序插入的,那么存一下上一次插入的串的节点为u,然后爬它的trans节点(设为q)尝试转移。但这个时候会出现一种情况就是,q这个节点把q的串和S'的串(设为p)的lcp(设为r)给缩起来成一条边了QAQ,这就很gay。

设v=par[q],假设我们知道了lcp是什么,那么我们就可以新建一个节点r表示lcp这个串,par[r] = v, par[p] = r, par[q] = r。(如果等于q就直接接儿子)这样每次加入一个后缀最多加入两个节点,那么我们的节点数显然是$O(n)$的,更准确的说就是2n

TIM截图20171228153545

然而lcp怎么求,设w为u向上爬(包括u)的第一个trans[x][c]不为NULL的节点,那么lcp(p,q)=c+w,仔细想想应该是对的。实际上证明的瓶颈在于那些被缩起来的点,然后注意到我们这是个东西的名字叫后缀自动机,我们都是先插入短后缀再插入长后缀的。如果在v所在的那条链上存在一个深度小于等于u接受态节点,那么这个玩意儿就可以被对应上,所以向上爬的第一个c+w就是lcp!

我来总结一下我上面说的吧:

  1. 上面我讲的东西是一个静态的。
  2. 由上面的讲解可以知道,SAM实际上可以解决掉后缀树的大部分题目
  3. SAM的空间损耗大概在$2\times S\times \sum len$,构造是线性的复杂度。
  4. 我们可以利用SAM构造出SA:在trans图上贪心遍历就好了
  5. 只要知道了一个串的长度和一个串在SAM上的状态序列就可以唯一地确定这个串
inline void malloc() { tr[++ tot] = node(); return tot; }

void ins(int c) {
    int x = lst, y = malloc(); lst = y;
    o.l = u.l + 1;
    for(; x && !v; x = u.p) v = y;

    if(!x) o.p = rt;
    else if(vn.l == u.l + 1) o.p = v;
    else {
        int z = malloc();
        tr[z].p = vn.p, tr[z].l = u.l + 1;
        memcpy(tr[z].trans, vn.trans, sizeof(tr[z].trans));
        vn.p = o.p = z;
        for(int ori = v; x && v == ori; x = u.p) v = z; 
    }
}

void build() {
    rt = lst = malloc();
    REP(i, 1, len) ins(buf[i] - 'a');
}

void init() { rt = lst = tot = 0; }

注意建图的时候接受态节点和非接受态节点的初始化区别(ノ´▽`)ノ♪


做完下面的基础题我相信你会对SAM有一个更深的认识,也会更清晰地认识到它的强大和优美,以至于你根本就不太想去看AC自动机这个东西了。

题目 Pt.I 狭义后缀自动机

Reference #0
Reference #1

下面我们来看几道基础题吧!

虽然感觉我这几道题都是偏统计类的。。。还没有什么dp的题目

SPOJ 1811 LCS

给两个长度$\leqslant10^5$的字符串 A 和 B,求出他们的最长公共连续子串。

我们拿第二个串在第一个串的SAM上面跑,能走trans就走trans,实在不行再走树边。注意维护一下实时的匹配长度就行了。

从这个题我们更深地理解一个事情就是SAM的一个节点维护的是它缩起来边上的所有的点的信息。

SPOJ 8222 Substring

首先有一个东西就是从后缀树这个角度理解,一个状态的在原串中的出现次数是它子树的接受态节点个数之和加一。

如果直接单纯拓扑序统计状态上的节点的len的贡献,就会发现一个问题,那就是我们刚刚1811在SAM上走到的状态只是它最大的状态,走到这个状态意味着它这条到根的parent链也都能被访问到,这些点并没有去更新,缩起来的边我们还没有统计,我们还需要在推上去的时候顺带统计掉他们的答案。但由于这道题的特殊性质,我们只需要这么干就可以了:

ans[len] = max(ans[len + 1], ans[len]);

是不是十分地机智。

这道题我们可以看出一个状态的在原串中的出现次数是它子树的接受态节点个数之和加一,一个状态如果被访问到,那么它的par也一定可以被访问到。对于长度排序其实和拓扑排序是一个意味的。

SPOJ 1812 LCS2

和1811一样,只不过有n个串儿而已。

如果直接在上一个做法的基础上对于每一个节点记一个min,然后做完n个串之后对全局的状态每个len记一个max,就会发现一个问题,那就是我们刚刚1811在SAM上走到的状态只是它最大的状态,走到这个状态意味着它这条到根的parent链也都能被访问到,这些点并没有去更新,和上一题不一样的是,在统计下一个串时候会受到影响,所以必须一个串做完就更新一遍。这个步骤我们没有必要边走边搞,我们可以在当前节点上打一个tag,然后最后按照拓扑序推上去就好了。

学到了一个打tag的技巧。

HDU 4622 Reincarnation

给出一个字符串,最长2000,q个询问,每次询问[l,r]区间内有多少个不同的子串。

这个题题解给出了一个很咸鱼的n^2做法。。。在n方时间内预处理出来一个表就行了,每一个ins一个字符的时候直接统计带来的贡献。

后缀数组可能还要带一个log,因为n方省略不了一个n,因为无论是SAM还是SA好像在我的认知范围内两头带修好像并不是这么好做。。。这意味着有n个后缀都要作出改动。

这个题告诉我们一个点所带来的不同子串的贡献是u.l - tr[u.p].l + 1;

不知道有什么更好的做法呢。

这个题看起来比另外几个还要咸鱼就没有写代码。

HDU 4436 str2int

我们沿用上一题的思路思考,想着能不能从后缀树这个方面思考,由于每个点和每个点的父亲之间缩起来的边就是本质不同的子串,可不可以预处理一个前缀和呢?发现这样好像不太好做,由于缩起来的边的存在,你很难在插入的时候预处理这个前缀和。

但这道题用后缀数组可谓是秒出做法,维护一个前缀和就好了,因为本质不同的子串在SA上可以很傻瓜式地体现出来,但SAM就不太一样了,通过前面我说的可以发现,由于许多的边都被压缩了起来,这就使事情没有这么好讨论了。不过有了前几道题的经验,这道题也应该很快就能出来。

回忆一下考虑我们走SAM的过程:能走trans就走trans,实在不行再走树边。又由于我们是边走边维护匹配长度的,这意味着一个点缩起来的边来源于走到他这里的trans。我们可以发现SAM上的一个节点实际上维护的是它被缩起来的那条边上的所有点的信息。那么这道题的做法就很明朗了:我们按照拓扑序走trans,一位一位更新,走的时候维护子串信息就行了。最后答案就是每个节点的和。

注意,分隔符不去转移。

这道题实际也是再次告诉我们SAM上一个状态路径和一个长度信息就可以确定一个唯一的子串。

POJ 3415 Common Substrings

给出两个串,问这两个串的所有的公共子串中(重复出现的,只要是位置不同就算两个子串),长度大于等于k的公共子串有多少个。

这道题用SA可谓是十分好做,考虑单调栈实际上是维护一段点到另一个端点之间的某个具有单调性的值的信息,用一个单调栈记录前缀贡献就好了,退栈的时候减去非法贡献(然而一开始我还在思考退栈的时候直接计算贡献然后没有记前缀导致我的复杂度爆炸。。。),现在我们来想一想SAM的做法。

还是沿着4622这个题目的思路,只要确定当前状态的最长匹配长度,利用par的长度和k的大小得到合法区间范围统计答案就行了,注意我们每次统计一个点的时候统计的都是一个状态带来的独立贡献。注意是最长匹配长度,所以parent链上的点也会出现,但是注意我们并不用每一个点都上去更新一遍,我们只需要拓扑序打个标记最后推一下标记就可以啦ヾ(◍°∇°◍)ノ゙

注意到这个题实际上并没有要求去重,所以我们还需要乘上一个出现次数的系数。这个系数就是子树和啦,拓扑更新一下就好了。

现在我们来思考一下如果要求去重怎么办。

要求去重的话,首先那个系数肯定不乘了。

然后父亲节点的标记只需要记录是否存在就行了(大概QAQ)。

至此,这道题就被我们完美解决啦,撒花✿✿ヽ(°▽°)ノ✿

SPOJ 7258 Lexicographical Substring Search

询问字典序第k大的子串。

SA上二分一下就行了,现在考虑SAM的做法。

考虑构建SA的过程,前序遍历,这意味着一个点的子树大小意味着以它为前缀后面还有多少比它大的。

那么如果子树大小大于k,这个点肯定在目标串里,那么print,-- k然后进入子树。

如果小于等于k,那么k -= u.sz,枚举下一棵子树就好了。

这个题懒得写了(


以上是SAM的一些经典的入门题目,大多是统计类的,还没有看到什么应用了DFA可转移dp这个常用的东西呢QAQ,还要找点题目。

有错误欢迎指出,您的一个微小举动可能拯救一个无知少女。

小结一下吧:

  1. SAM的一个节点维护的是它缩起来边上的所有的点的信息。
  2. 一个状态如果被访问到,那么它的par也一定可以被访问到。
  3. 对于长度排序其实和拓扑排序是一个意味的。
  4. 打tag的技巧。
  5. 一个点所带来的不同子串的贡献是u.l - tr[u.p].l + 1;
  6. SAM上一个状态路径和一个长度信息就可以确定一个唯一的子串。
  7. SAM前序遍历可以构造出SA。
  8. SAM考虑问题的时候可以从ST,SAM两个角度入手,ST是点与par的缩起来的边的关系,可以考虑树形dp或者类似的东西,SAM则是子串一位一位的转移。
  9. 一个套路是考虑在SAM上跑当前状态可以匹配的最长路径,然后打tag更新它的par
  10. SA那个单调栈的技巧

SAM实在是太优美啦φ(๑>ω<๑)~~~

下面我来口胡一些题目

口胡题解

以下是口胡内容。

为什么截止到目前我遇到的SAM题基本都长一个样儿。。。。。已经懒得再写差不多的代码了QAQ

CF 235C

给出一个字符串s,这里称之为母串,然后再给出n个子串,n<=10^5,子串长度总和不超过10^6。问,对于每一个子串的所有不同的周期性的同构串在母串中出现的次数总和。

对于一个询问,把最后一个字符删掉然后接起来,之后跑一下,然后该统计答案统计答案就行了。注意重复子串算入贡献,所以预处理一个right

CF 427D

给出两个长度均不超过5000的字符串s1,s2,求这两个串中,都只出现一次的最短公共子串。

第二个串在上面跑的时候打点标记然后拓扑推一下,之后统计满足要求的最短的就行了

BZOJ 4566 HAOI2016找相同字符

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

跑SAM的时候肯定是有一个缩起来的边的贡献,乘上一个right,最后不要忘记推par的标记,一个点的贡献不要忘记只是统计单点带来的贡献

BZOJ 3998 TJOI2015 弦论

第k大子串,可重和不可重

SAM的做法就不说了,SA的做法。。。等我去学习一个。。。

BZOJ 3576 APIO2014 回文串

题面都懒得写了= =

听说是回文自动机裸题,可惜我不会。
这个题学到了一个技巧叫做倍增2333333

一会儿去写写
其实这个题应该放在回文双子星那里。

BZOJ 3238 AHOI2013 差异

懒得写题面

SA:单调栈,注意ht相同时候的处理就行了,和Common String那个题一样,不过写这个题的SA做法还不如去写那个题的SA做法
SAM:从后缀树的角度拓扑统计答案就行啦

Upd on 2018/1/9 这个题被我写啦,写了个SAM做法

BZOJ 4199 NOI2015 品酒大会

懒得写题面

SAM做法看题秒。

想想SA吧!受到Common Strings这个题的影响,一开始的时候,我想了一个十分鬼畜的单调栈+rmq的东西。。就是,我们考虑单调栈这个东西可以让我们知道某一段到当前点的某个单调的东西的信息情况,那么我们利用这个东西统计,像Common String一样,难点还是在于前缀贡献的处理。这个问题你仔细一想,发现,实际上这玩意儿是重复叠加了好几遍的,所以我们可以通过记录当前点在什么时候入栈的,从而在弹栈的时候再处理它的贡献就行啦,而且当前点对应的rk一定是一个连续的区间,那么ht很好维护,这道题就被我们完美解决啦!我真是个天才

但是看了看网上好像全写的是并查集。。。。只找到了一个 和我脑洞差不多的人 写了这个做法

下面我来说一下正常的做法吧,看到这种区间最大最小值一个是单调栈一个就是并查集嘛(上回在wangyy的noip题里面学习的做法),离线降序插入ht,合并sa中相邻的两位,然后合并的时候多合并一个minmax这题不就做完了嘛(

然后你就发现了一个事情,实际上并查集这个做法和SAM本质上是一样的,相当于也是对于每一个lca(lcp)去合并子树,只不过SA并没有实际把这个树直接建出来,而是边统计边建的,真是有趣呀。

BZOJ 2882 工艺

超级懒得写题面

没什么可说的。。。这个题要注意的一个事情就是用map建后缀自动机了QAQ

BZOJ 4180 字符串识别

这看起来是道不错的题呀,终于看到一个正常的题目了。。。。。

可惜我不会= =

第二天UPD:终于会了这道题,可惜bzoj上目前还是WA的。。。。。。。网上讲得非常清楚。感觉是一道不错的SAM题,最起码不是和上面那些题长得差不多了。。。。。。

BZOJ 4032

行吧。。。字符串暴力四合一。。
为啥还能出到省选里的。。。。

认识了一个新东西叫序列自动机。就是trans边变成了它后面这个字符第一次出现的地方,一个状态的par是它上回出现的地方。
ins的时候顺着par向上爬,把没有trans的改成它就行了。

狭义后缀自动机剩下马下来还没看的题目:

  • BZOJ 2806
  • HDU 5470

题目 Pt.II 广义后缀自动机

恩。。可惜我还不会广义后缀自动机。。。过会儿去看看。。。回头补上

UPD:离线的可以直接BFS,在线的话由于长度不是单调的,直接ins的话找lcp可能会出现一点问题,因为新插入的一个点可能成为某个老点的父亲。

在线的我还不太会呜呜呜

· EOF ·

Comments
Write a Comment