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 的大作中提到】
: 用trie做吗？
|
p*****2
发帖数: 21240 | 4
把所有的substring写到trie里的话就是n^2复杂度吧？
【在 d****o 的大作中提到】
: 具体讲讲，怎么可以比O(n^3)快
|
w****x
发帖数: 2483 | 5
用rolling hash的思想就是O(n^2)
【在 p*****2 的大作中提到】
:
: 把所有的substring写到trie里的话就是n^2复杂度吧？
|
p*****2
发帖数: 21240 | 6
rolling hash啥思想呀？给个summary吧。
【在 w****x 的大作中提到】
:
: 用rolling hash的思想就是O(n^2)
|
d****o
发帖数: 1055 | 7 对，把每一个substring都hash到一个hash_map里面去，就是O(n^2)
但是这个space是 O(n^2)
【在 p*****2 的大作中提到】
:
: rolling hash啥思想呀？给个summary吧。
|
p*****2
发帖数: 21240 | 8
hash的时间复杂度是O(1)吗？
【在 d****o 的大作中提到】
: 对，把每一个substring都hash到一个hash_map里面去，就是O(n^2)
: 但是这个space是 O(n^2)
|
w****x
发帖数: 2483 | 9
还是n^3吧
【在 p*****2 的大作中提到】
:
: hash的时间复杂度是O(1)吗？
|
d****o
发帖数: 1055 | 10 http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
这里说有O(n)的方法，哪位大侠给解释一下。多谢。
【在 d****o 的大作中提到】
: 对，把每一个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 的大作中提到】
:
: 还是n^3吧
|
p*****2
发帖数: 21240 | 12
他这个算法跟我说的差不多呀。
【在 d****o 的大作中提到】
: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
: 这里说有O(n)的方法，哪位大侠给解释一下。多谢。
|
w****x
发帖数: 2483 | 13
是啊，rolling嘛
【在 p*****2 的大作中提到】
:
: 他这个算法跟我说的差不多呀。
|
p*****2
发帖数: 21240 | 14
没研究过。感觉hash跟字符串的长度有关吧。
【在 w****x 的大作中提到】
:
: 是啊，rolling嘛
|
l*****a
发帖数: 14598 | 15 trie就是o(n)
why 用那些不常见的
【在 p*****2 的大作中提到】
:
: 没研究过。感觉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 的大作中提到】
: 这个题用suffix array 比较好做啊。 programming pearl chapter 15章的内容。 O（
: nlongn).
|
i***e
发帖数: 452 | 18 如果用radix sort strings？ 那么这个可以是O（n)?
【在 l*****a 的大作中提到】
: 数组sort就是nlgn
: 你字符串sort算是n^2*lgn吧
|
d****o
发帖数: 1055 | 19 你说啥了？
【在 p*****2 的大作中提到】
:
: 没研究过。感觉hash跟字符串的长度有关吧。
|
p*****2
发帖数: 21240 | 20
刚才出去游泳想了一下。是可以做到的
【在 w****x 的大作中提到】
:
: 是啊，rolling嘛
|
|
|
r**********g
发帖数: 22734 | 21 标准算法吧
construct suffix tree
find deepest internal node
trace from root
O(n)
【在 p*****2 的大作中提到】
:
: 刚才出去游泳想了一下。是可以做到的
|
p*****2
发帖数: 21240 | 22
刚才看了一下。construct suffix tree好写吗？从来没写过呀。
【在 r**********g 的大作中提到】
: 标准算法吧
: construct suffix tree
: find deepest internal node
: trace from root
: O(n)
|
r**********g
发帖数: 22734 | 23 O(n)的不是很好写。Google一下，很长
【在 p*****2 的大作中提到】
:
: 刚才看了一下。construct suffix tree好写吗？从来没写过呀。
|
p*****2
发帖数: 21240 | 24
那面试碰到不是要跪吗？LZ说一下这题是要思路还是写代码呢？我觉得我用trie写个n^
2的还有可能。
【在 r**********g 的大作中提到】
: O(n)的不是很好写。Google一下，很长
|
r**********g
发帖数: 22734 | 25 我觉得值得一学。suffix tree搞好了以后无数东西都解决了
n^
【在 p*****2 的大作中提到】
:
: 那面试碰到不是要跪吗？LZ说一下这题是要思路还是写代码呢？我觉得我用trie写个n^
: 2的还有可能。
|
g**e
发帖数: 6127 | 26 如果不用写build suffix tree代码的话还是可以写一下的
n^
【在 p*****2 的大作中提到】
:
: 那面试碰到不是要跪吗？LZ说一下这题是要思路还是写代码呢？我觉得我用trie写个n^
: 2的还有可能。
|
p*****2
发帖数: 21240 | 27
嗯。有时间好好学学。
【在 r**********g 的大作中提到】
: 我觉得值得一学。suffix tree搞好了以后无数东西都解决了
:
: n^
|
l*****a
发帖数: 14598 | 28 放心吧，没有任何人在面试中被要求写这个
除非就是不想要你
【在 p*****2 的大作中提到】
:
: 嗯。有时间好好学学。
|
p*****2
发帖数: 21240 | 29
是。不想要的话，怎么也没辙。
【在 l*****a 的大作中提到】
: 放心吧，没有任何人在面试中被要求写这个
: 除非就是不想要你
|
d****o
发帖数: 1055 | 30 我还是好好看一下suffix tree吧。怎么没有懂呢。
n^
【在 p*****2 的大作中提到】
:
: 是。不想要的话，怎么也没辙。
|
|
|
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 的大作中提到】
: 好奇的问问大家。
: 我刚才翻了一下CLRS，上边没有介绍suffix tree。你们是什么时候学的呢？做
: research还是准备面试呢？我看suffix tree的面试题其实也很少。
|
p*****2
发帖数: 21240 | 34
我记得你给我发过，不过当时扫了一眼，没怎么看，因为觉得面试不会碰到。
【在 l*****a 的大作中提到】
: 有一次研究重复子串/最长子串的题目，在网上查到一篇文章
: 才知道这些题目都可以用suffix tree解决
|
l*****a
发帖数: 14598 | 35 万一哪次你碰上因此没拿到offer，估计你就下工夫看看了
【在 p*****2 的大作中提到】
:
: 我记得你给我发过，不过当时扫了一眼，没怎么看，因为觉得面试不会碰到。
|
p*****2
发帖数: 21240 | 36
是。看了一下，你那个链接还在。今天扫一遍。
【在 l*****a 的大作中提到】
: 万一哪次你碰上因此没拿到offer，估计你就下工夫看看了
|
d****o
发帖数: 1055 | 37 求分享
【在 p*****2 的大作中提到】
:
: 是。看了一下，你那个链接还在。今天扫一遍。
|
c*****e
发帖数: 3226 | 38 求链接。谢！
【在 d****o 的大作中提到】
: 求分享
|
l*****a
发帖数: 14598 | 39 no code there.
http://varsoft.iteye.com/blog/874650
【在 d****o 的大作中提到】
: 求分享
|
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 的大作中提到】
: 数组sort就是nlgn
: 你字符串sort算是n^2*lgn吧
|
b*******y
发帖数: 2048 | 42 niu!
【在 i***e 的大作中提到】
: 这个题用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 的大作中提到】
: 你说的对，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构造都很麻烦，面试碰到肯定是不用写了。 |
