m****1
发帖数: 41 | |
j********x
发帖数: 2330 | 2 Suffix tree
弄一个大suffixtree 放所有单词后缀，后缀树上的从root出发的所有路径就是全部
unique 的子串 遍历并且计数
比如考虑当前路径从root到leaf长度为n，则其子串数目为n，每个分支另行统计 |
p*****2
发帖数: 21240 | |
m****1
发帖数: 41 | 4 但是worst case是字串的数目无法track,数目可以相当巨大，因为每个字符串长度可以
是2000，而且有50个这样的字符串，怎么保证能在3秒内对所有子串进行排序 和 检索
呢？
我还没想明白，可以详细说说么，谢谢哈
【在 j********x 的大作中提到】
: Suffix tree
: 弄一个大suffixtree 放所有单词后缀，后缀树上的从root出发的所有路径就是全部
: unique 的子串 遍历并且计数
: 比如考虑当前路径从root到leaf长度为n，则其子串数目为n，每个分支另行统计
|
m****1
发帖数: 41 | 5 非牛，只是对interviewstreet一直有关注，这两天做了一些string的，正好看到这题
，没有思路了。。
【在 p*****2 的大作中提到】
: 大牛简单题目都做完了？
|
m****1
发帖数: 41 | 6 感觉Interviewstreet的水挺深，有几题特别难，其他的慢慢做可以摸出来。
有一题叫queen revised..那叫一个bt..
【在 p*****2 的大作中提到】
: 大牛简单题目都做完了？
|
C*********r
发帖数: 21 | 7 1. for each string sort suffix, klnk * n, k is string size, n is number of
strings
2. merge sort suffix from step 1
correct? |
