Kasai 算法从后缀数组构建 LCP 数组

后缀数组

特定字符串的所有后缀都排列在后缀数组中。这个概念与后缀树类似，后缀树是所有文本后缀的压缩树。

后缀数组是许多处理字符串算法中使用的基本数据结构。它显示了一个给定字符串的所有后缀按字典序排列的数组。使用最有效的方法构建后缀数组所需的时间复杂度通常为 O(n log n)，其中 n 是输入文本的长度。

LCP 数组

给定字符串 S 的后缀数组伴随着一个称为 LCP 数组（最长公共前缀数组）的数组。它详细说明了后缀排序顺序中后续后缀之间的最长公共前缀的长度。

后缀数组是一个整数数组 sa[0..n-1]，其中 sa[i] 表示当字符串 S 的后缀按字典序排序时，位置 i 的后缀的起始索引。给定长度为 n 的字符串 S，后缀数组是一个整数数组 sa[0..n-1]。

LCP 数组是一个整数数组 lcp[0..n-1]，其中整数 lcp[i] 表示排序顺序中起始索引为 sa[i] 和 sa[i+1] 的后缀之间的最长公共前缀的长度。

与后缀数组类似，LCP 数组是一个大小为 n 的数组。值 lcp[i] 表示由 suffix[i] 和 suffix[i+1] 索引的后缀之间的最长公共前缀的长度。由于后面没有后缀，因此 suffix[n-1] 未定义。

Kasai 算法

在“Kasai 算法”的上下文中讨论了最长公共前缀 (LCP) 问题，这是字符串处理和字符串算法中的一个基本问题。这个挑战是最长公共子串问题的一个变体。

最长公共前缀 (LCP) 问题的目标是查找一组字符串中最长的公共前缀。例如，字符串 ["apple", "appetizer", "append", and "appreciate"] 中最长的公共前缀是 "app."

“Kasai 算法”经常用于解决此问题。Kasai 技术是一种线性时间技术，它从给定文本的后缀数组创建 LCP 数组。该术语首次由 Tatsuya Kasai 等人在其题为“后缀数组中的线性时间最长公共前缀计算及其应用”的文章中使用。

算法

• 对于给定字符串，创建后缀数组。
• 通过遍历后缀数组来比较后续后缀。
• 应确定每对连续后缀（suffix[i] 和 suffix[i+1]）之间公共前缀的长度。
• LCP 数组是一个存储公共前缀长度的数组。

示例

考虑字符串 S = "banana"。

• 对于 S，创建后缀数组。

字符串 S = "banana" 具有以下后缀数组

后缀数组 (sa)

[5, 3, 1, 0, 4, 2]

• 将反向后缀数组设置为零。

反向后缀数组 inv 将包含后缀数组中每个后缀的位置。例如，inv 将是

反向后缀数组 (inv)

[3, 2, 5, 1, 4, 0]

• 将 LCP 数组 lcp 的所有元素初始化为 0。

LCP 数组 (lcp)

[0, 0, 0, 0, 0, 0]

• 应用 Kasai 算法计算 LCP 数组。

对于 i = 0

sa[0] = 5, inv[5] = 0, k = 0。

更新 lcp[0] = 0。

对于 i = 1

sa[1] = 3, inv[3] = 1, k = 0。

比较后缀 "na"（从索引 3 开始）和 "ana"（从索引 1 开始）。未找到公共前缀。

更新 lcp[1] = 0。

对于 i = 2

sa[2] = 1, inv[1] = 2, k = 0。

比较后缀 "ana"（从索引 1 开始）和 "banana"（从索引 0 开始）。未找到公共前缀。

更新 lcp[2] = 0。

对于 i = 3

sa[3] = 0, inv[0] = 3, k = 0。

比较后缀 "banana"（从索引 0 开始）和 "nana"（从索引 4 开始）。找到长度为 1 的公共前缀 ("n")。

更新 lcp[3] = 1。

对于 i = 4

sa[4] = 4, inv[4] = 4, k = 0。

比较后缀 "nana"（从索引 4 开始）和 "a"（从索引 2 开始）。未找到公共前缀。

更新 lcp[4] = 0。

对于 i = 5

sa[5] = 2, inv[2] = 5, k = 0。

比较后缀 "a"（从索引 2 开始）和 "banana"（从索引 5 开始）。未找到公共前缀。

更新 lcp[5] = 0。

最终的 LCP 数组是 [0, 0, 0, 1, 0, 0]。