1. 简介
后缀数组是处理字符串的一种强有力工具,高效而且容易编程实现,可应用于求字符串的多种子串问题中,可谓处理字符串的一大利器。
2. 思想
2.1 子串
字符串 S S S 的子串 s [ i . . j ] , i ≤ j s[i..j], \ i \leq j s [ i .. j ] , i ≤ j 表示串 S S S 中从第 i i i 个字符到第 j j j 个字符形成的字符串。
2.1.1 重复子串
字符串 s s s 在字符串 S S S 中至少出现两次,则称 s s s 为 S S S 的重复子串。
可重叠重复子串:即重复子串间可以重叠部分子字符串。
不可重叠重复子串:即重复子串间不可以有部分重叠的子字符串。
2.1.2 回文子串
字符串 S S S 的子串 s s s 满足 i n v e r s e ( s ) = s
inverse(s) = s
in v erse ( s ) = s ,则称 s s s 为 S S S 的回文子串。
2.1.3 公共子串
如果字符串 s s s 同时出现在字符串 S A SA S A 和 S B SB SB 中,则称字符串 s s s 为字符串 S A SA S A 和 S B SB SB 的公共子串。
2.2 前缀 & 后缀
前缀 是指从串开头到第 i i i 个字符形成的特殊子串,字符串 S S S 以第 i i i 个字符结尾的前缀表示为 p r e f i x ( i ) prefix(i) p re f i x ( i ) 。类似地,后缀 是指从第 i i i 个字符开始到串结尾形成的特殊子串,字符串 S S S 以第 i i i 个字符开始的后缀表示为 s u f f i x ( i ) suffix(i) s u ff i x ( i ) 。
2.3 后缀数组
后缀数组 s a sa s a 保存的是字符串 S S S 的 n n n 个后缀(n n n 为字符串 S S S 的长度)从小到大排好序后的后缀开头字符在 S S S 中的下表位置。即 s a [ i ] sa[i] s a [ i ] 表示排名第 i i i 大的后缀的首字符位置。
2.4 名次数组
名次数组 r k rk r k 保存的是后缀 s u f f i x ( i ) suffix(i) s u ff i x ( i ) 排序后的排名。
【注】
易知后缀数组 s a sa s a 和 r k rk r k 满足 s a [ r k [ i ] ] = i , r k [ s a [ i ] ] = i
sa[rk[i]] = i , \
rk[sa[i]] = i
s a [ r k [ i ]] = i , r k [ s a [ i ]] = i 。故已知其中一者,可以在 O ( n ) O(n) O ( n ) 时间内求出另一者。
2.5 高度数组
高度数组 h e i g h t height h e i g h t 保存的是排名相邻的两个后缀的最长公共前缀,即 h e i g h t [ i ] = s u f f i x ( s a [ i − 1 ] )
height[i] = suffix(sa[i-1])
h e i g h t [ i ] = s u ff i x ( s a [ i − 1 ]) 和 s u f f i x ( s a [ i ] ) suffix(sa[i]) s u ff i x ( s a [ i ]) 的最长公共前缀。
对于 j j j 和 k k k ,设 r k [ j ] < r k [ k ]
rk[j] \lt rk[k]
r k [ j ] < r k [ k ] ,则有性质:s u f f i x ( j ) suffix(j) s u ff i x ( j ) 和 s u f f i x ( k ) suffix(k) s u ff i x ( k ) 的最长公共前缀为 h e i g h t [ r k [ j ] + 1 ] , h e i g h t [ r k [ j ] + 2 ] , ⋯ , h e i g h t [ r k [ k ] ]
height[rk[j]+1],height[rk[j]+2],\cdots,height[rk[k]]
h e i g h t [ r k [ j ] + 1 ] , h e i g h t [ r k [ j ] + 2 ] , ⋯ , h e i g h t [ r k [ k ]] 中的最小值。
定义 h h h 数组:h [ i ] = h e i g h t [ r k [ i ] ] h[i] = height[rk[i]] h [ i ] = h e i g h t [ r k [ i ]]
则有性质:h [ i ] ≥ h [ i − 1 ] − 1
h[i] \geq h[i-1] - 1
h [ i ] ≥ h [ i − 1 ] − 1 。
证明
h [ i − 1 ] = h e i g h t [ r k [ i − 1 ] ]
h[i-1] = height[rk[i-1]]
h [ i − 1 ] = h e i g h t [ r k [ i − 1 ]] 是 s u f f i x ( s a [ r k [ i − 1 ] − 1 ] ) suffix(sa[rk[i-1]-1]) s u ff i x ( s a [ r k [ i − 1 ] − 1 ]) 和 s u f f i x ( s a [ r k [ i − 1 ] ] ) suffix(sa[rk[i-1]]) s u ff i x ( s a [ r k [ i − 1 ]]) 的最长公共前缀,不妨设
s u f f i x ( s a [ r k [ i − 1 ] − 1 ] ) = a A B s u f f i x ( s a [ r k [ i − 1 ] ] ) = a A C \begin{array}{c}
suffix(sa[rk[i-1]-1]) = aAB \\
suffix(sa[rk[i-1]]) = aAC
\end{array}
s u ff i x ( s a [ r k [ i − 1 ] − 1 ]) = a A B s u ff i x ( s a [ r k [ i − 1 ]]) = a A C
则
h [ i − 1 ] = ∣ a A ∣ h[i-1] = |aA| h [ i − 1 ] = ∣ a A ∣ ,且 s u f f i x ( s a [ r k [ i − 1 ] − 1 ] ) suffix(sa[rk[i-1]-1]) s u ff i x ( s a [ r k [ i − 1 ] − 1 ]) 排在 s u f f i x ( s a [ r k [ i − 1 ] ] ) suffix(sa[rk[i-1]]) s u ff i x ( s a [ r k [ i − 1 ]]) 前面。又
s a [ r k [ i ] ] = i = i − 1 + 1 = s a [ r k [ i − 1 ] ] + 1 \begin{array}{c}
sa[rk[i]] = i = i-1 + 1 = sa[rk[i-1]] + 1
\end{array}
s a [ r k [ i ]] = i = i − 1 + 1 = s a [ r k [ i − 1 ]] + 1
故 s u f f i x ( s a [ r k [ i ] ] ) = A C suffix(sa[rk[i]]) = AC s u ff i x ( s a [ r k [ i ]]) = A C 。又
s u f f i x ( s a [ r k [ i − 1 ] − 1 ] + 1 ) = A B \begin{array}{c}
suffix(sa[rk[i-1]-1]+1) = AB
\end{array}
s u ff i x ( s a [ r k [ i − 1 ] − 1 ] + 1 ) = A B
故此二者的最长公共前缀为
∣ A ∣ = h [ i − 1 ] − 1 \begin{array}{c}
|A| = h[i-1] - 1
\end{array}
∣ A ∣ = h [ i − 1 ] − 1
且因为 s u f f i x ( s a [ r k [ i − 1 ] − 1 ] ) suffix(sa[rk[i-1]-1]) s u ff i x ( s a [ r k [ i − 1 ] − 1 ]) 排在 s u f f i x ( s a [ r k [ i − 1 ] ] ) suffix(sa[rk[i-1]]) s u ff i x ( s a [ r k [ i − 1 ]]) 前面,故 s u f f i x ( s a [ r k [ i − 1 ] − 1 ] + 1 ) suffix(sa[rk[i-1]-1]+1) s u ff i x ( s a [ r k [ i − 1 ] − 1 ] + 1 ) 排在 s u f f i x ( s a [ r k [ i − 1 ] ] + 1 ) = s u f f i x ( s a [ r k [ i ] ] )
suffix(sa[rk[i-1]]+1) = suffix(sa[rk[i]])
s u ff i x ( s a [ r k [ i − 1 ]] + 1 ) = s u ff i x ( s a [ r k [ i ]]) 前面。根据上一个性质可知,后缀 A C AC A C 和 A B AB A B 的最长公共前缀为排名在二者之间的后缀与后缀 A B AB A B 的最长公共前缀的最小值,即
h [ i − 1 ] − 1 ≤ h e i g h t [ r k [ i ] ] = h [ i ] \begin{array}{c}
h[i-1] - 1 \leq height[rk[i]] = h[i]
\end{array}
h [ i − 1 ] − 1 ≤ h e i g h t [ r k [ i ]] = h [ i ]
证毕。
3. 实现
3.1 求后缀数组
倍增法(复杂度 O ( n lg n ) O(n \lg n) O ( n lg n ) )
用倍增的方法对每个字符开始的长度为 2 k 2^k 2 k 的子字符串进行排序。然后合并相邻两个子字符串时将前后两个子字符串的排名看作是两个数位,利用基数排序进行排序,得到以每个字符开始的长度为 2 k + 1 2^{k+1} 2 k + 1 的子字符串的排名,以此类推。直到当 2 k > n 2^k \gt n 2 k > n 时,每个字符开始的长度为 2 k 2^k 2 k 的子字符串便相当于所有的后缀,即得到最终的后缀数组。
【注】具体实现细节参考下文中的代码。
3.2 求高度数组
利用高度数组的性质,求 h [ i ] h[i] h [ i ] 时,由于 h [ i ] ≥ h [ i − 1 ] − 1
h[i] \geq h[i-1] - 1
h [ i ] ≥ h [ i − 1 ] − 1 ,即 s u f f i x ( s a [ r k [ i ] ] ) suffix(sa[rk[i]]) s u ff i x ( s a [ r k [ i ]]) 和 s u f f i x ( s a [ r k [ i ] − 1 ] ) suffix(sa[rk[i]-1]) s u ff i x ( s a [ r k [ i ] − 1 ]) 的最长公共前缀至少为 h [ i − 1 ] − 1 h[i-1]-1 h [ i − 1 ] − 1 ,故可以直接根据上一步计算出的 h [ i − 1 ] h[i-1] h [ i − 1 ] ,然后直接从 s t r [ s a [ r k [ i ] ] + h [ i − 1 ] − 1 ] str[sa[rk[i]]+h[i-1]-1] s t r [ s a [ r k [ i ]] + h [ i − 1 ] − 1 ] 与 s t r [ s a [ r k [ i ] − 1 ] + r k [ i ] − 1 ] str[sa[rk[i]-1]+rk[i]-1] s t r [ s a [ r k [ i ] − 1 ] + r k [ i ] − 1 ] 处开始继续往后枚举,判断是否还有公共部分。
【注】具体实现细节参考下文中的代码。
4. 模板
4.1 倍增法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 #include <bits/stdc++.h> using namespace std;#ifndef _SUFFIXARRAY_ #define _SUFFIXARRAY_ #define ll int #define MAXN 1200000 #define MAXCNT 130 struct SuffixArray { ll n; ll sa[MAXN]; ll rk[MAXN]; ll ssa[MAXN]; ll srk[MAXN]; ll cnt[MAXCNT]; ll height[MAXN]; void doubling (char *str, ll m) { ll i, j, k; ll *prk = rk, *psrk = srk; n = strlen (str) + 1 ; for (i = 0 ; i < m; ++i) cnt[i] = 0 ; for (i = 0 ; i < n; ++i) ++cnt[prk[i] = str[i]]; for (i = 1 ; i < m; ++i) cnt[i] += cnt[i-1 ]; for (i = n-1 ; ~i; --i) sa[--cnt[str[i]]] = i; for (j = 1 , k = 1 ; k < n; j <<= 1 , m = k) { for (i = n-j, k = 0 ; i < n; ++i) ssa[k++] = i; for (i = 0 ; i < n; ++i) if (sa[i] >= j) ssa[k++] = sa[i] - j; for (i = 0 ; i < n; ++i) psrk[i] = prk[ssa[i]]; for (i = 0 ; i < m; ++i) cnt[i] = 0 ; for (i = 0 ; i < n; ++i) ++cnt[psrk[i]]; for (i = 1 ; i < m; ++i) cnt[i] += cnt[i-1 ]; for (i = n-1 ; ~i; --i) sa[--cnt[psrk[i]]] = ssa[i]; swap (prk, psrk); for (prk[sa[0 ]] = 0 , k = 1 , i = 1 ; i < n; ++i) { prk[sa[i]] = (psrk[sa[i-1 ]]==psrk[sa[i]] && psrk[sa[i-1 ]+j]==psrk[sa[i]+j]) ? k-1 : k++; } } } void generateHeight (char *str) { ll i, j, k = 0 ; for (i = 0 ; i < n; ++i) rk[sa[i]] = i; for (i = 0 ; i < n-1 ; height[rk[i++]] = k) for (k?k--:0 , j = sa[rk[i]-1 ]; str[i+k] == str[j+k]; ++k); } }; #endif