SA & SAM

事先说明：以下所有字符串的下标从1开始

SA

[OI-WIKI链接](后缀数组简介 - OI Wiki)

是什么

SA要干的是这样一件事：

有一个字符串s，维护s每个后缀的字典序排名

也就是说：我们要对每个 \(1\le i\le n\) ，将 \(s[i,n]\) 按照字典序进行排序,

得到两个数组 \(sa\) 和 \(rk\)

其中

\(sa_i\) 表示字典序排名第 \(i\) 个的后缀的左端点

\(rk_i\) 表示 \(s[i,n]\) 这个后缀在所有后缀中的字典序排名

这也是SA中最重要的两个数组

引入一张OI-WIKI的图：

然后这两个数组还有两个性质：

\(sa[rk[i]]=i,rk[sa[i]]=i\)

那么如何做SA呢？

怎么做

这里给出一种 \(O(nlog^2n)\) 的倍增做法，其实还有更快的 \(O(nlogn)\) 和 \(O(n)\) 做法，但似乎 \(O(nlog^2n)\) 就够用了 (OI-WIKI说的)

还是一张OI-WIKI的图

过程：

1. 将每个 \(s[i,i]\) ，也就是每个 \(s[i]\) 按照字典序排序，得到第一层的 \(sa\) 和 \(rk\)

2. 将每个 \(s[i,i+1]\) ，也就是每两个字符组成的子串按照字典序排序，注意到这时rk数组代表了每个字符的字典序大小，所以我们可以将 \(s[i,i+1]\) 分成 \(s[i,i]\) 和 \(s[i+1,i+1]\) 两部分，用 \(rk\) 数组来排序：如果 \(rk[i]=rk[j]\) ,那么比较 \(rk[i+1]\) 和 \(rk[j+1]\) ，否则比较 \(rk[i]\) 和 \(rk[j]\) （这就是cmp过程）。这样我们就可以得到第二层的 \(sa\) 和 \(rk\)

   （插一句话：我们要相信世间人人以真诚相待，美好永存）

3. 将每个 \(s[i,i+3]\) ，也就是每四个字符组成的子串按照字典序排序，这时我们依旧可以仿照2中的方法，将 \(s[i,i+3]\) 分成 \(s[i,i+1]\) 和 \(s[i+2,i+3]\) 两部分，通俗一点讲就是把长度为4的子串拆成两个长度为2的子串，由于我们已知第二层的 \(rk[i]\) 和 \(rk[i+2]\) ，也就是长度为2的子串的字典序排名，然后用 \(rk[i],rk[j],rk[i+2],r[j+2]\) 来排序：如果 \(rk[i]=rk[j]\) ,那么比较 \(rk[i+2]\) 和 \(rk[j+2]\) ，否则比较 \(rk[i]\) 和 \(rk[j]\) （感觉和分治很像，先把左右两个区间处理好，再处理当前区间）

​ ...

就这样一直到算到有一个数 \(k\) ，使得 \(1+2^k>n\) 为止 ，这样就算出了最终的sa和rk

为什么

那么SA可以用来干什么呢？

（可移步OI-WIKI）

1. 求一个字符串循环位移的字典序排序（最小的循环位移不就是最小表示法嘛，\(O(n)\) 求就行了）
2. 从字符串首尾取字符最小化字典序

height数组

\(height[i]=lcp(s[sa[i],n],s[sa[i-1],n])\)

就是排名第 \(i\) 个的后缀和它前一名的后缀的最长公共前缀

有一个结论：\(height[rk[i]]\ge height[rk[i-1]]-1\)

（不会证，懒得证，复习的我看过来，补一下这里）

然后就可以根据这个结论 \(O(n)\) 求 \(height\)

用处可移步OI-WIKI

SAM

。。。

下面引入一段对话来证明SAM的有用程度

那么SAM有什么用呢？

用处很多。

那么SAM可以用来做什么呢？

多了去了，等你看到题就知道了。