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
|
|
