c*********t
发帖数: 2921 | 1 Hi,
I have a question about Longest repeated substring.
Given a string "BANANA", is the longest repeated substring "ANA" or just "AN
" or "NA"?
According to the definition in Wikipedia. It seems that the longest repeated
string is "ANA".
http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
http://en.wikipedia.org/wiki/Suffix_tree
I guess this is how it works for these two different answers.
For the answer ANA
BANANA
|||
|||
Here ANA is repeated twice. However these two ANA overlap | j*****h
发帖数: 62 | 2 Programming pearls里好像是提到过这个问题，没记错的化，它是用suffix array
来作的。算法很简单，假设string长度为n,以‘\0'结尾。开辟一个字符指针数组长度
为n，每个指针依次指向string的一个suffix。把该数组看成n个字符串的数组，排序。
再scan一遍，找相邻两个字符串最长的common prefix，即可。复杂度O(n^2lgn).
这种算法是允许overlap的，也就是说'ANA'是BANANA的最长重复子串。
AN
repeated
【在 c*********t 的大作中提到】
: Hi,
: I have a question about Longest repeated substring.
: Given a string "BANANA", is the longest repeated substring "ANA" or just "AN
: " or "NA"?
: According to the definition in Wikipedia. It seems that the longest repeated
: string is "ANA".
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
: http://en.wikipedia.org/wiki/Suffix_tree
: I guess this is how it works for these two different answers.
: For the answer ANA
|
|
