Microsoft(3) 最长重复子串

//Given a input string find the longest substring which appears more than once in the string?

除了trie(suffix)tree, 还有什么其他解法，code出来，给出时间空间复杂度，不同解法对比

没人会吗，好的，可以用trie tree

按照昨天那个thread里的说法，可以用后缀数组，然后对每两个相邻的suffix取LCA，最长的那个就是。
这题和昨天那个差不多，就是输入变成了一个串，并且出现次数限制放宽，用trie还是一样能做，但复杂度就是n^2了。后缀树感觉什么都能做到O(n)但太复杂就不说了。用nlogn的后缀数组应该是个不错的选择

回复 2# wwwyhx

用trie tree也算么？
我以为n^2的算法都不行@@。。。

有种解法是把字符串所有后缀取出，排序放入一个一维数组，然后两两比较最大前缀。解决方案挺neat的，不知道是不是楼上说的后缀数组

wwwyhx 发表于 2011-4-22 20:09
有种解法是把字符串所有后缀取出，排序放入一个一维数组，然后两两比较最大前缀。解决方案挺neat的，不知道 ...

再进一步，就是后缀数组了。不过，到这里，就足够解决这个问题了。

可以先找出所有后缀，然后排序，再求相邻的字符串的最大前缀