-
後綴數組
鎖定
在計算機科學裏, 後綴數組(英語:suffix array)是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。
- 中文名
- 後綴數組
- 外文名
- Suffix Array
- 子 串
- 字符串 S 的子串
後綴數組簡介
在計算機科學裏,後綴數組(英語:suffix array)是一個通過對字符串的所有後綴經過排序後得到的數組。此數據結構被運用於全文索引、數據壓縮算法、以及生物信息學。
後綴數組定義
令字符串
,
表示S的子字符串,下標從i到j。
後綴數組例子
考慮字符串S=banana$:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
[i] | b | a | n | a | n | a | $ |
字符串的結尾是特殊字符$,用作特殊標誌。該字符串有以下後綴:
後綴 | i |
---|---|
banana$ | 1 |
anana$ | 2 |
nana$ | 3 |
ana$ | 4 |
na$ | 5 |
a$ | 6 |
$ | 7 |
後綴經過升序排序後:
後綴 | i |
---|---|
$ | 7 |
a$ | 6 |
ana$ | 4 |
anana$ | 2 |
banana$ | 1 |
na$ | 5 |
nana$ | 3 |
後綴數組A包含這些後綴的起始位置:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
A[i] | 7 | 6 | 4 | 2 | 1 | 5 | 3 |