【啊哈，算法】之十、后缀数组，求最长重复子串

转自：http://blog.csdn.net/hackbuteer1/article/details/7968623

直观的解法是，首先检测长度为 n - 1 的字符串情况，如果不存在重复则检测 n - 2, 一直递减下去，直到 1 。

这种方法的时间复杂度是 O(N * N * N)，其中包括三部分，长度纬度、根据长度检测的字符串数目、字符串检测。

利用后缀数组
后缀数组是一种数据结构，对一个字符串生成相应的后缀数组后，然后再排序，排完序依次检测相邻的两个字符串的开头公共部分。
这样的时间复杂度为：生成后缀数组 O(N)，排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)
依次检测相邻的两个字符串 O(N * N)，总的时间复杂度是 O(N^2*logN)，优于第一种方法的 O(N^3)

demo如下：

其中：当作为comlen函数参数的两个字符串长度相等时，该函数便返回这个长度值，从第一个字符开始

#include <iostream>#include <list>using namespace std;//思路：用一个数组保存字符出现的次数。用i和j进行遍历整个字符串。//当某个字符没有出现过，次数+1；出现字符已经出现过，次数+1，找到这个字符前面出现的位置的下一个位置，设为i//并将之前的那些字符次数都-1。继续遍历，直到'\0'int find(char str[],char *output){int i = 0 , j = 0;int cnt[26] = {0};int res = 0 , temp = 0;char *out = output;int final;while(str[j] != '\0'){if(cnt[str[j]-'a'] == 0){cnt[str[j]-'a']++;}else{cnt[str[j]-'a']++;while(str[i] != str[j]){cnt[str[i]-'a']--;i++;}cnt[str[i]-'a']--;i++;}j++;temp = j-i;if(temp > res){res = temp;final = i;}}//结果保存在output里面for(i = 0 ; i < res ; ++i)*out++ = str[final++];*out = '\0';return res;}int main(void){char a[] = "abcdefg";char b[100];int max = find(a,b);cout<<b<<endl;cout<<max<<endl;return 0;}