后缀数组

发表于 | 阅读数

$Suffix\ Array$

数组定义

  • $suf(i)$表示从$[i,len]$这段长度的字符串，也就是字符串的后缀
  • $rank[i]$表示$suf(i)$在所有后缀中排名第几，排名按照字典序排名。
  • $sa[i]$表示排名第$i$位的后缀是$suf(sa[i])$。

后缀数组

将所有后缀排序按字典序确定这些数组。

例如$ababa$

  • $a$
  • $aba$
  • $ababa$
  • $ba$
  • $baba$

若使用快排复杂度为$O(n\log n *strcmp)$，由于$strcmp$,过于麻烦。所以需要其他算法。

倍增算法

先对$1$个字符排序
| a | b | a | b | a |
| —- | —- | —- | —- | —- |
| 1 | 2 | 1 | 2 | 1 |
再对$\leq2$个字符排序的时候，就可以直接用之前的排名进行插排序对所有之前排名$1$的再进行排序，桶排的思想开始。
| ab | ba | ab | ba | a |
| —- | —- | —- | —- | —- |
| 12 | 21 | 12 | 21 | 10 |
| 2 | 3 | 2 | 3 | 1 |
再对$\leq4$个字符排序的时候,只需要把上一个表拿来当之前的排名，继续前后组合。（注意$1$跟$3$组合,$2$和$4$组合）
| abab(a) | baba | aba | ba | a |
| ———- | —— | —— | —— | —— |
| 1212 | 2121 | 1210 | 2100 | 1000 |
| 3 | 5 | 2 | 4 | 1 |
最后排到排名没有不同即可，（所以对于那些所有数字不一样，只需要排序一次即可，根据字典序的定义，这样就是对的）。

实现

  • $tn[i]$表示有多少组并列排名第$i$。
  • $y[i]$第二关键字排名第$i$,对应的他需要拼接前面那个字符的位置。

根据第一关键字判断第二关键字大小。
没有第二关键字的字一定最小

1
2
3
4
5
for (int i = len - k + 1; i <= len; i++)
    y[++cnt] = i;
for (int i = 1; i <= len; i++)
    if (sa[i] > k)
        y[++cnt] = sa[i] - k;

例如：（$k=2$)
| ab | ba | ab | ba | a |
| —- | —- | —- | —- | —- |
| 12 | 21 | 12 | 21 | 10 |
| 2 | 3 | 2 | 3 | 1 |

y数组

1 2 3 4 5
4(ba) 5(a) 3(ab) 1(ab) 2(ba)

然后先对第一关键字先处理

1
2
3
4
5
6
for (int i = 1; i <= len; i++)
    tn[ra[i]]++;
for (int i = 1; i <= size; i++)
    tn[i] += tn[i - 1];
for (int i = len; i >= 1; i--) 
    sa[tn[ra[y[i]]]--] = y[i];

按第二关键字从大到小，第二关键字越靠后在同一个桶里的排名越大，这就是倒着枚举的原因。

然后根据$sa[i]$倒推出$rank[i]$

1
2
3
4
cnt = 1;
ra[sa[1]] = 1;
for (int i = 2; i <= len; i++)
    ra[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? cnt : ++cnt;

顺便完成去重复的任务,如果所有排名不重复就后缀数组已经完成。

Height 数组的求法

定义$LCP(x,y)$,表示$suf(rank[x])$与$suf(rank[y])$最长公共前缀。

例如$abababa$,$LCP(3,5)=3$。

由于后缀数组是字典排序，相近的一定会排在一起。则显然

我们就设$height[i]=LCP(i,i-1)$
例如：

  • $a$ 0
  • $aba$ 1
  • $ababa$ 3
  • $ba$ 0
  • $baba$ 2

求法

设一个辅助数组$h[i]=height[rank[i]]$
| a | b | a | b | a |
| —- | —- | —- | —- | —- |
| 3 | 2 | 1 | 0 | 0 |
证明：$h[i]>=h[i-1]-1$

$h[i-1]<=1,显然成立$
$h[i-1]>=2$
$设k=sa[rank[i-1]-1],h[i-1]=lcp(rank[i-1],rank[k])$

$lcp(rank[i],rank[k+1])=h[i-1]-1\leq lcp(rank[i],rank[i]-1)=h[i]$

这样就可以先确定$height[i]$最小值，然后暴力匹配,$h[i]$是可以滚动的就不需要数组。

复杂度$O(n)$，不会计算。

1
2
3
4
5
6
7
8
9
10
11
12
int k = 0;
for (int i = 1; i <= len; i++)
    ra[sa[i]] = i;
for (int i = 1; i <= len; i++)
{
    if (k)
        k--;
    int j = sa[ra[i] - 1];
    while (i + k <= len && j + k <= len && s[j + k] == s[i + k])
        k++;
    he[ra[i]] = k;
}