l******c 发帖数: 2555 | 1 write a program that finds all repeated substrings in the string and provide
the complexity of this program. how can you make it to perform better in
time and memory | m*****g 发帖数: 226 | | l******c 发帖数: 2555 | 3 I have no idea.
This is a yahoo interview question. I need an anwer asap | P********l 发帖数: 452 | 4 suppose Si=one substring that make of the whole string.
Now the question is to find n that whole string = n * Si
give an array of prime numbers = {2,3,5,7,11,...} try to divide and check if
the Si is the substring. For example, whole string = 2 * S1 = 5 * S2 = 7 *
S3. and no other way to divide it.
Then the smallest sub string is divide the whole string into 2 * 5 * 7
pieces.
For example, UUUUUU = UU . UU . UU = UUU . UUU.
good luck.
provide
`
【在 l******c 的大作中提到】 : write a program that finds all repeated substrings in the string and provide : the complexity of this program. how can you make it to perform better in : time and memory
| l******c 发帖数: 2555 | 5 Do not understand,
for string "abcab", the repeated substring should be "a", "b", "ab", how to
apply your algorithm
if
*
【在 P********l 的大作中提到】 : suppose Si=one substring that make of the whole string. : Now the question is to find n that whole string = n * Si : give an array of prime numbers = {2,3,5,7,11,...} try to divide and check if : the Si is the substring. For example, whole string = 2 * S1 = 5 * S2 = 7 * : S3. and no other way to divide it. : Then the smallest sub string is divide the whole string into 2 * 5 * 7 : pieces. : For example, UUUUUU = UU . UU . UU = UUU . UUU. : good luck. :
| s********l 发帖数: 998 | 6 all repeated substring?
suppose we have a string like this "abcdabc"
should "ab" be considered as one? how about "a"?
to
【在 l******c 的大作中提到】 : Do not understand, : for string "abcab", the repeated substring should be "a", "b", "ab", how to : apply your algorithm : : if : *
| P********l 发帖数: 452 | 7 In that case, use surfix tree.
for example, tabcab, the surfix tree is:
b -cab
ab -cab
cab
tabcab
in the construction of the surfix tree you can find the substrings.
to
【在 l******c 的大作中提到】 : Do not understand, : for string "abcab", the repeated substring should be "a", "b", "ab", how to : apply your algorithm : : if : *
| r****o 发帖数: 1950 | 8 什么时候用suffix tree, 什么时候用prefix tree呢?
好像两个都可以用于字符串匹配的问题。
【在 P********l 的大作中提到】 : In that case, use surfix tree. : for example, tabcab, the surfix tree is: : b -cab : ab -cab : cab : tabcab : in the construction of the surfix tree you can find the substrings. : : to
| r****c 发帖数: 2585 | 9 两个应用不同啊
suffix tree一般用来表达一个或多个string internal, like substring of a string
prefix tree (trie) 只是表达几个strings' substring which starts from
beginning
【在 r****o 的大作中提到】 : 什么时候用suffix tree, 什么时候用prefix tree呢? : 好像两个都可以用于字符串匹配的问题。
| r****o 发帖数: 1950 | 10 那能用prefix tree的场合应该也可以用suffix tree吧?
string
【在 r****c 的大作中提到】 : 两个应用不同啊 : suffix tree一般用来表达一个或多个string internal, like substring of a string : prefix tree (trie) 只是表达几个strings' substring which starts from : beginning
| f*********5 发帖数: 576 | 11 suffix tree :basically store one string at its suffix string array
prefix tree(Trie): store a number of strings.
for my understanding, suffix tree will be used to substring related issues
while trie/prefix tree will be used to store a large number of data,for
example,
dictionary
【在 r****o 的大作中提到】 : 那能用prefix tree的场合应该也可以用suffix tree吧? : : string
|
|