本文介绍了Ukkonen算法构造后缀树、如何用后缀数组构造后缀数组从而得到一个$O(n)$构造后缀数组的算法(不考虑字符集大小)，并与其他~~优秀的~~后缀数组算法进行了速度比较。

食用本文前建议对后缀数组(SA)和后缀树(ST)有基本了解。

前言

为什么要学习Ukkonen算法？

P.S.: 附后缀树动态演示网站方便理解和调试检查。

基本思路

Ukkonen算法的目标是构建一棵后缀树: 所有后缀组成的Trie，且没有分支的串会被压缩(每条边是一个子串而不再只是一个字符)，下图就是串dbabbaa的后缀树。

dbabbaa

Ukkonen算法类似于构建后缀自动机(SAM)，采用增量法: 在线构造每次末尾插入一个字符利用旧的后缀树维护出新的后缀树。

插入一个字符

插入一个字符似乎所有后缀都变了，但是实际上只是每个后缀加了一个字符，怎么快速维护？

核心是怎么快速维护后缀树所有边的子串？既然是子串维护左右端点就可以了，因此每条边上的子串可以记为$[l,r]$。

这样插入一个字符就是所有$r = n$的子串$r++$。那么只需要每条边记录它是不是$r = n$就好了，这样每次$n++$以后根本都不需要修改。事实上，更简单的是: 所有$r = n$的边都是叶子节点和它父亲的连边。

~~于是我们就做完了。~~

并没有，这样会遇到一个问题。

出现重复字符

例如dbabbaa在准备插入第四个字符dbab的时候就会有问题，按照后缀树的定义后缀b和bab应该被压缩在一起。

这里先不处理，特判一下: 记录下从根节点出发走过一个串b后所停留的位置将来有可能需要拆出一个点。这样我们没有对后缀树做任何操作，实际上根本就没有插入最后一个后缀b。

这里还需要记录一个rem表示有多少个这种没有插入的后缀，如果出现了这种特判情况，自然要rem++。目前的特判只有这么一条，我们说根节点(特判记录出发的点)是活动节点。

dbab

实现过程中一般采取每插入一个字符(将要插入一个新后缀)就rem++，直到插入一个后缀成功后rem--，而特判记录不属于插入成功。

特判记录以后显然什么都不能做了，需要停止操作等待下一个输入字符。

拆点

接下来输入第五个字符dbabb的时候出现了分叉，那么刚刚记下的”将来有可能需要拆点”就变成了现实，那么就执行拆点操作。注意这个拆点操作是在实质性插入第五个字符之前发生的。

dbabb

然后成功插入了后缀b，rem--。所有后缀都插入了，第五个字符就插入完成了。

目前得到的是一棵隐式后缀树(后缀不一定都在叶子节点结束，例如新插入的后缀b在节点4结束)而非显式后缀树(后缀都在叶子节点结束)。

既然已经插入了第五个字符产生了一个分叉，不难发现第六个字符x会构成后缀bx，即使是x要导致拆点也一定会先从图中的4号节点分叉(当然可能同时也会在别的节点比如根节点分叉)，因此将活动点改为4号点表示如果再要特判记录的话一定是先从4开始。

dbabba

link边

继续插入第六个字符(特判记录)dbabba。

dbabba

注意输入第六个字符完以后下一个字符可能的分叉ax又是从根节点开始了，活动节点调整为根节点。

然而这个调整时怎么进行的？怎么知道该调整到哪个节点？

这类似于AC自动机的fail指针，更类似于后缀自动机的link指针。这里每个点记录一个link边，表示当前后缀删除首字母会到达哪个后缀，因为叶子节点都是已经成功插入的后缀，所以link都是根节点，同时由于link用于调整活动节点，活动节点一定是分裂出来的点(因为叶子总是$r = n$的，叶子永远不会再成为内部节点)，因此只有活动节点可能被link到。

如果构建了link以后，那么现在输入一个新字符活动节点沿着link跳就行了。

然后输入第七个字符发现需要拆点dbabbaa，就可以直接从根节点拆了。

Talk is Cheap

说起来很容易，考虑怎么实现。

首先对于一个后缀树节点需要记录以下信息: c(x,y)表示节点x读入字符y会到达的节点(c(x,y)连向父亲x的边上的子串首字母是y)，beg(x)表示x连向x的父亲的边上的子串起始下标，len(x)表示x连向x的父亲的边上的子串长度(其中叶子节点不需要长度)，link(x)表示x的link指针。

下面是一个节点定义的代码，其中m表示当前已经插入的字符串总长，tot用于分配节点，s处理已经插入的字符串(str是原串),last表示活动节点，rem表示剩余没有插入的后缀，用New新建一个节点:

#define MAXN 100000
#define c(x,y) t[x].c[y]
#define beg(x) t[x].beg
#define len(x) t[x].len
#define link(x) t[x].link
struct Node{int c[27],beg,len,link;}t[(MAXN<<1)+5]; int s[MAXN+5], m, tot, last, rem; char str[MAXN+5];
#define New(b,l) (++tot, beg(tot) = b, len(tot) = l, link(tot) = 1, tot)

然后考虑增量法，首先s[++m] = x, ++rem插入一个新字符。

总结一下所有的操作: 每次要么成功插入一个新的后缀(rem--)并继续操作，要么沿着边走并特判记录，要么拆点并继续操作。

Claim: 被特判记录的一定是活动节点对应的字符串开始的连续一段后缀。

每次成功插入的新后缀都是从活动节点出发，而活动节点根据link移动，link对应的下标单调递增的(根据定义删掉首字母)。所以特判记录总是一个队列，先被记录的先被成功插入。

有了这个性质就可以首先沿着既有的后缀树边行走，找到输入字符被卡到哪条边上:

1	for(; rem > len(c(last,s[m-rem+1])); rem -= len(last=c(last,s[m-rem+1])));

当活动节点移动的时候后缀就相当于已经被加入到隐式后缀树的内部节点中了，所以rem中可以去掉它们。

然后考虑活动节点的分支(因为特判记录是连续后缀所以s[m-rem+1]是活动节点出边开始的字符):

1	int &p = c(last,s[m-rem+1]);

如果没有这样一个点，就是新建一个点(叶子没有长度记为INF)，成功插入一个新后缀，然后调整link(将上一个活动节点或插入节点的link连接到现在的活动节点，同样是由于link的单调性和活动节点的单调性):

1	if(!p) p = New(m-rem+1,INF), q = link(q) = last;

如果有这样一个点，而且下一步可以沿着边走下去，就是特判记录，因为last已经记录活动节点rem已经记录位置信息，所以什么也不用做，调整link就结束即可:

1	else if(x==s[beg(p)+rem-1]){q = link(q) = last; break;}

如果有这样一个点，但是下一步不能沿着边走下去，就需要拆点，新建一个(之前准备要)拆出来的点，然后新建一个走出去的点，修改一下长度，修改一下link即可:

1	else nq = New(beg(p),rem-1), c(nq,x) = New(m,INF), c(nq,s[beg(p)+=rem-1]) = p, len(p) -= rem-1, q = link(q) = p = nq;

于是就完成了增量法构造:

inline void Append(int x){
    for(int q = (s[++m]=x,++rem,1), nq; rem; last>1?last=link(last):--rem){
        for(; rem > len(c(last,s[m-rem+1])); rem -= len(last=c(last,s[m-rem+1]))); int &p = c(last,s[m-rem+1]);
        if(!p) p = New(m-rem+1,INF), q = link(q) = last; else if(x==s[beg(p)+rem-1]){q = link(q) = last; break;}
        else nq = New(beg(p),rem-1), c(nq,x) = New(m,INF), c(nq,s[beg(p)+=rem-1]) = p, len(p) -= rem-1, q = link(q) = p = nq;
    }
}

注意Ukkonen算法目前为止生成了隐式后缀树，有些后缀可能停止在内部节点。那么可以通过结尾增加一个不存在的字符来保证每个后缀都分叉出一个叶子节点。

后缀树构造后缀数组

和SAMSA步骤几乎是一样的。

首先构造后缀树，添加不存在字符，然后桶排:

1
2
3

Append(0); for(rint i = 1, j; i <= tot; i++) for(j = 0; j <= 26; c(i,j)?fa[c(i,j)]=i:0, j++); memset(fir+1,-1,tot<<2);
book[0] = 1; for(rint i = 2; i <= tot; ++book[s[beg(i)]], i++); for(rint i = 1; i <= 26; book[i] += book[i-1], i++);
for(rint i = tot; i; o[book[s[beg(i)]]--] = i, i--); for(rint i = tot; i>1; Add(fa[o[i]],o[i]), i--); DFS(1,0); CalHeight();

SAMSA构造出的后缀树用end(i)+maxlen(link(i))来找到边的首字母，但是Ukkonen算法构建出的后缀树自带beg(i)。不过Ukkonen算法需要自己维护出fa，不过这不太困难。

DFS略有不同，Ukkonen算法没有维护mx，可以通过记录总长度和最后叶子的beg(叶子没有长度)来获得后缀的真实位置:

1	void DFS(int p){mx(p) ? SA[Rank[end(p)]=++rk] = end(p) : 0; for(rint u = first[p], v; ~u; DFS(e[u].to), u = e[u].nex);}

Show Me the Code

完整Ukkonen算法构建后缀树进而构造后缀数组:

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define INF 0x3f3f3f3f
#define c(x,y) t[x].c[y]
#define beg(x) t[x].beg
#define len(x) t[x].len
#define link(x) t[x].link
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
struct Node{int c[27],beg,len,link;}t[(MAXN<<1)+5]; int s[MAXN+5], SA[MAXN+5], Rank[MAXN+5], Height[MAXN+5], n, m, tot, last, rem; char str[MAXN+5];
#define New(b,l) (++tot, beg(tot) = b, len(tot) = l, fir[tot] = -1, link(tot) = 1, tot)
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[(MAXN<<2)+5]; int fir[(MAXN<<1)+5], fa[(MAXN<<1)+5], o[(MAXN<<1)+5], book[27], etot, rk;
inline void Add(int a, int b){e[etot] = Edge(b,fir[a]), fir[a] = etot++;}
inline void Append(int x){
    for(int q = (s[++m]=x,++rem,1), nq; rem; last>1?last=link(last):--rem){
        for(; rem > len(c(last,s[m-rem+1])); rem -= len(last=c(last,s[m-rem+1]))); int &p = c(last,s[m-rem+1]);
        if(!p) p = New(m-rem+1,INF), q = link(q) = last; else if(x==s[beg(p)+rem-1]){q = link(q) = last; break;}
        else nq = New(beg(p),rem-1), c(nq,x) = New(m,INF), c(nq,s[beg(p)+=rem-1]) = p, len(p) -= rem-1, q = link(q) = p = nq;
    }
}
void DFS(int p, int d){if(len(p)>n) SA[Rank[beg(p)-d]=rk++] = beg(p)-d; else{d += len(p); for(rint u = fir[p]; ~u; DFS(e[u].to,d), u = e[u].nex);}}
void CalHeight(){for(rint i = 1, L = 0, j; i <= n; Height[Rank[i++]] = L) for(j = SA[~-Rank[i]], L-=L>0; i+L<=n&&j+L<=n&&s[i+L]==s[j+L]; ++L);}
int main(){
    scanf("%s",str+1); n = strlen(str+1); last = ++tot; len(0) = INF; for(rint i = 1; i <= n; Append(str[i]-'a'+1), i++);
    Append(0); for(rint i = 1, j; i <= tot; i++) for(j = 0; j <= 26; c(i,j)?fa[c(i,j)]=i:0, j++); memset(fir+1,-1,tot<<2);
    book[0] = 1; for(rint i = 2; i <= tot; ++book[s[beg(i)]], i++); for(rint i = 1; i <= 26; book[i] += book[i-1], i++);
    for(rint i = tot; i; o[book[s[beg(i)]]--] = i, i--); for(rint i = tot; i>1; Add(fa[o[i]],o[i]), i--); DFS(1,0); CalHeight();
    for(rint i = 1; i <= n; printf("%d%c",SA[i],"\n "[i<n]), i++); for(rint i = 2; i <= n; printf("%d%c",Height[i],"\n "[i<n]), i++); return 0;
}

上述代码可以直接通过UOJ#35 后缀排序。

在附加相同的读入优化且不使用输出优化情况下: 倍增方法约为$350\;\text{ms}$；SAMSA方法约为$330\;\text{ms}$；SA-IS方法约为$250\;\text{ms}$；Ukkonen方法约为$400 \sim 500\;\text{ms}$。

在附加相同的读入输出优化情况下: 倍增方法约为$210\;\text{ms}$；SAMSA方法约为$250\;\text{ms}$；SA-IS方法约为$100\;\text{ms}$；Ukkonen方法约为$250 \sim 350\;\text{ms}$。

在稳定的评测鸭上测试同一套数据得到的数据(这里应该是最慢数据点): 倍增方法$28.535\;\text{ms}$；SAMSA方法$46.304\;\text{ms}$；SA-IS方法约为$9.68\;\text{ms}$；Ukkonen方法约为$49.624\;\text{ms}$。

所以Ukkonen方法果然是又慢又复杂(代码挺好写的但是个人感觉很容易出错)。

所以Ukkonen方法果然是又慢又复杂。

扫描二维码即可在手机上查看这篇文章，或者转发二维码来分享这篇文章: