最长重复子串算法解决方案

【出自TX笔试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个字符串，找出这个字符串中最长的重复子串，比如给定字符串“banana”，子字符串“ana”出现2次，因此最长的重复子串为“ana”。

分析与解答：

由于题目要求最长重复子串，显然可以先求出所有的子串，然后通过比较各子串是否相等从而求出最长公共子串，具体的思路是：首先找出长度为n-1的所有子串，判断是否有相等的子串，如果有相等的子串，那么就找到了最长的公共子串；否则找出长度为n-2的子串继续判断是否有相等的子串，依次类推直到找到相同的子串或遍历到长度为1的子串为止。这种方法的思路比较简单，但是算法复杂度较高。下面介绍一种效率更高的算法：后缀数组法。(www.xing528.com)

后缀数组是一个字符串的所有后缀的排序数组。后缀是指从某个位置i开始到整个串末尾结束的一个子串。字符串r从第i个字符开始的后缀表示为Suffix（i），也就是Suffix（i）=r[i..len（r）]。例如：字符串“banana”的所有后缀如下：

所以“banana”的后缀数组为{5，3，1，0，4，2}。由此可以把找字符串的重复子串的问题转换为从后缀排序数组中。通过对比相邻的两个子串的公共串的长度。在上例中3：ana与1：anana的最长公共子串为ana。这也就是这个字符串的最长公共子串。实现代码如下：

算法性能分析：

这种方法在生成后缀数组的复杂度为O（N），排序的算法复杂度为O（Nlog2N），最后比较相邻字符串的操作的时间复杂度为O（N），所以算法的时间复杂度为O（Nlog2N）。此外，由于申请了长度为N的额外的存储空间，因此空间复杂度为O（N）。