d****o 发帖数: 1055 | 1 the longest repeated substring problem is the problem of finding the longest
substring of a string that occurs at least twice.
比如
input: banana
ouput: ana
bruth force way是O(n^3),我只做出来这个,弱啊。
哪位大牛来解释一下? |
p*****2 发帖数: 21240 | |
d****o 发帖数: 1055 | 3 具体讲讲,怎么可以比O(n^3)快
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用trie做吗?
|
p*****2 发帖数: 21240 | 4
把所有的substring写到trie里的话就是n^2复杂度吧?
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 具体讲讲,怎么可以比O(n^3)快
|
w****x 发帖数: 2483 | 5
用rolling hash的思想就是O(n^2)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 把所有的substring写到trie里的话就是n^2复杂度吧?
|
p*****2 发帖数: 21240 | 6
rolling hash啥思想呀?给个summary吧。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 用rolling hash的思想就是O(n^2)
|
d****o 发帖数: 1055 | 7 对,把每一个substring都hash到一个hash_map里面去,就是O(n^2)
但是这个space是 O(n^2)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : rolling hash啥思想呀?给个summary吧。
|
p*****2 发帖数: 21240 | 8
hash的时间复杂度是O(1)吗?
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,把每一个substring都hash到一个hash_map里面去,就是O(n^2) : 但是这个space是 O(n^2)
|
|
w****x 发帖数: 2483 | 9
还是n^3吧
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : hash的时间复杂度是O(1)吗?
|
d****o 发帖数: 1055 | 10 http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
这里说有O(n)的方法,哪位大侠给解释一下。多谢。
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对,把每一个substring都hash到一个hash_map里面去,就是O(n^2) : 但是这个space是 O(n^2)
|
|
|
p*****2 发帖数: 21240 | 11
input: banana
ouput: ana
应该是n^2
把banana
anana
nana
ana
na
a
写到trie里不是n^2吗?写的时候就可以判断是不是最长了。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 还是n^3吧
|
p*****2 发帖数: 21240 | 12
他这个算法跟我说的差不多呀。
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://en.wikipedia.org/wiki/Longest_repeated_substring_problem : 这里说有O(n)的方法,哪位大侠给解释一下。多谢。
|
w****x 发帖数: 2483 | 13
是啊,rolling嘛
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 他这个算法跟我说的差不多呀。
|
p*****2 发帖数: 21240 | 14
没研究过。感觉hash跟字符串的长度有关吧。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是啊,rolling嘛
|
l*****a 发帖数: 14598 | 15 trie就是o(n)
why 用那些不常见的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 没研究过。感觉hash跟字符串的长度有关吧。
|
i***e 发帖数: 452 | 16 这个题用suffix array 比较好做啊。 programming pearl chapter 15章的内容。 O(
nlongn). |
l*****a 发帖数: 14598 | 17 数组sort就是nlgn
你字符串sort算是n^2*lgn吧
【在 i***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题用suffix array 比较好做啊。 programming pearl chapter 15章的内容。 O( : nlongn).
|
i***e 发帖数: 452 | 18 如果用radix sort strings? 那么这个可以是O(n)?
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 数组sort就是nlgn : 你字符串sort算是n^2*lgn吧
|
d****o 发帖数: 1055 | 19 你说啥了?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 没研究过。感觉hash跟字符串的长度有关吧。
|
p*****2 发帖数: 21240 | 20
刚才出去游泳想了一下。是可以做到的
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是啊,rolling嘛
|
|
|
r**********g 发帖数: 22734 | 21 标准算法吧
construct suffix tree
find deepest internal node
trace from root
O(n)
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 刚才出去游泳想了一下。是可以做到的
|
p*****2 发帖数: 21240 | 22
刚才看了一下。construct suffix tree好写吗?从来没写过呀。
【在 r**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 标准算法吧 : construct suffix tree : find deepest internal node : trace from root : O(n)
|
r**********g 发帖数: 22734 | 23 O(n)的不是很好写。Google一下,很长
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 刚才看了一下。construct suffix tree好写吗?从来没写过呀。
|
p*****2 发帖数: 21240 | 24
那面试碰到不是要跪吗?LZ说一下这题是要思路还是写代码呢?我觉得我用trie写个n^
2的还有可能。
【在 r**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : O(n)的不是很好写。Google一下,很长
|
r**********g 发帖数: 22734 | 25 我觉得值得一学。suffix tree搞好了以后无数东西都解决了
n^
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 那面试碰到不是要跪吗?LZ说一下这题是要思路还是写代码呢?我觉得我用trie写个n^ : 2的还有可能。
|
g**e 发帖数: 6127 | 26 如果不用写build suffix tree代码的话还是可以写一下的
n^
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 那面试碰到不是要跪吗?LZ说一下这题是要思路还是写代码呢?我觉得我用trie写个n^ : 2的还有可能。
|
p*****2 发帖数: 21240 | 27
嗯。有时间好好学学。
【在 r**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得值得一学。suffix tree搞好了以后无数东西都解决了 : : n^
|
l*****a 发帖数: 14598 | 28 放心吧,没有任何人在面试中被要求写这个
除非就是不想要你
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 嗯。有时间好好学学。
|
p*****2 发帖数: 21240 | 29
是。不想要的话,怎么也没辙。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 放心吧,没有任何人在面试中被要求写这个 : 除非就是不想要你
|
d****o 发帖数: 1055 | 30 我还是好好看一下suffix tree吧。怎么没有懂呢。
n^
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。不想要的话,怎么也没辙。
|
|
|
s*********e 发帖数: 197 | 31 用suffix array,可以有O(nlogn)。在programming pearls第二版的15.2有详细讨论。 |
p*****2 发帖数: 21240 | 32 好奇的问问大家。
我刚才翻了一下CLRS,上边没有介绍suffix tree。你们是什么时候学的呢?做
research还是准备面试呢?我看suffix tree的面试题其实也很少。 |
l*****a 发帖数: 14598 | 33 有一次研究重复子串/最长子串的题目,在网上查到一篇文章
才知道这些题目都可以用suffix tree解决
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好奇的问问大家。 : 我刚才翻了一下CLRS,上边没有介绍suffix tree。你们是什么时候学的呢?做 : research还是准备面试呢?我看suffix tree的面试题其实也很少。
|
p*****2 发帖数: 21240 | 34
我记得你给我发过,不过当时扫了一眼,没怎么看,因为觉得面试不会碰到。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有一次研究重复子串/最长子串的题目,在网上查到一篇文章 : 才知道这些题目都可以用suffix tree解决
|
l*****a 发帖数: 14598 | 35 万一哪次你碰上因此没拿到offer,估计你就下工夫看看了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我记得你给我发过,不过当时扫了一眼,没怎么看,因为觉得面试不会碰到。
|
p*****2 发帖数: 21240 | 36
是。看了一下,你那个链接还在。今天扫一遍。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 万一哪次你碰上因此没拿到offer,估计你就下工夫看看了
|
d****o 发帖数: 1055 | 37 求分享
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是。看了一下,你那个链接还在。今天扫一遍。
|
c*****e 发帖数: 3226 | 38 求链接。谢!
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求分享
|
l*****a 发帖数: 14598 | 39 no code there.
http://varsoft.iteye.com/blog/874650
【在 d****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 求分享
|
f*****n 发帖数: 15 | 40 one way to solve it is to use DP. runtime is O(n^2) and it requires O(n)
extra space.
import java.util.ArrayList;
import java.util.List;
public class StringOperation {
public static void main(String[] args) {
StringOperation strOp = new StringOperation();
System.out.println(strOp.findLongRepeatedString("banana"));
System.out.println(strOp.findLongRepeatedString("aaaaa"));
}
public String findLongRepeatedString(String src) {
Result longestResult = null;
List repeatedStrs = new ArrayList();
for(int i = 1; i < src.length(); i++) {
List newRepeatedStrs = new ArrayList
Result>();
for (Result result : repeatedStrs) {
if(src.charAt(result.endIndex+1) == src.charAt(i)) {
Result r = new Result();
r.startIndex = result.startIndex;
r.endIndex = result.endIndex+1;
newRepeatedStrs.add(r);
if(longestResult == null) {
longestResult = r;
} else if(r.length() > longestResult.length()) {
longestResult = r;
}
}
}
for(int j = 0; j < i; j++) {
if(src.charAt(j) == src.charAt(i)) {
Result r = new Result();
r.startIndex = j;
r.endIndex = j;
newRepeatedStrs.add(r);
if(longestResult == null) {
longestResult = r;
}
}
}
repeatedStrs = newRepeatedStrs;
}
if(longestResult == null) {
return null;
} else {
return src.substring(longestResult.startIndex, longestResult.
endIndex + 1);
}
}
private class Result {
private int startIndex;
private int endIndex;
public int length() {
return endIndex - startIndex;
}
}
} |
|
|
b*****o 发帖数: 715 | 41 你说的对,programming pearls的作者在这里犯了个错误。他假设两个字符串比较只需
要O(1)。而实际上最坏情况是O(1)。
但是貌似suffix tree的算法在最坏情况也是O(n^2)。因为build tree的时候,每次两
个子字符串比较最坏也可能需要O(n)。
一个这样子的例子就是全a串"aaaaa.....aaa"。两个suffix string比较时间平均是n/2。
这使suffix array和suffix tree的最坏时间复杂度分别是O(n^2 log(n))和O(n^2)。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 数组sort就是nlgn : 你字符串sort算是n^2*lgn吧
|
b*******y 发帖数: 2048 | 42 niu!
【在 i***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题用suffix array 比较好做啊。 programming pearl chapter 15章的内容。 O( : nlongn).
|
c****g 发帖数: 85 | 43 刚好我也看到programming pearls这章。
string sorting 需要O(n^2*logn)?不是吧。而是和平均字符串d相关。
string array的结构满简单,容易理解的。还没看suffix tree。貌似没书讲,只能
google了。
/2。
【在 b*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你说的对,programming pearls的作者在这里犯了个错误。他假设两个字符串比较只需 : 要O(1)。而实际上最坏情况是O(1)。 : 但是貌似suffix tree的算法在最坏情况也是O(n^2)。因为build tree的时候,每次两 : 个子字符串比较最坏也可能需要O(n)。 : 一个这样子的例子就是全a串"aaaaa.....aaa"。两个suffix string比较时间平均是n/2。 : 这使suffix array和suffix tree的最坏时间复杂度分别是O(n^2 log(n))和O(n^2)。
|
c****x 发帖数: 15 | 44 suffix array和suffix tree构造都很麻烦,面试碰到肯定是不用写了。 |