string - 最长后缀-前缀重叠算法

Question

我的任务是确定一个有效的算法 [O(n*log(n))]，给定一组 k 字符串 S = {s-1, s-2, s-3, ..., sk}，将为每对字符串 (si, sj) 识别最长的子串 T，使得 T 是 si 的后缀和 sj 的前缀，以及每对字符串 (sj, si) 的最长子串 T。n 表示所有 k 个字符串的相加长度 (n = |s-1| + |s-2| + |s-3| + ... + |sk|)。

有什么想法吗？一个解决方案的链接也可以。提前致谢！

Answer 1

Algorithmic Aspects of Bioinformatics一书第 61 页的算法 4.10提供了一种使用后缀树计算一组给定字符串的最长公共子字符串的方法

该文章还解释了如何找到最长的公共子字符串

关于后缀树大小的线性时间，即O(n log n)。