专家们，find the longest common substring of two strings - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

专家们，find the longest common substring of two strings

专家们，find the longest common substring of two strings# JobHunting - 待字闺中

I*A2010-07-11 07:07

1 楼

不许用DP,suffix tree
http://en.wikipedia.org/wiki/Longest_common_substring_problem
笨法子是什么？

f*52010-07-11 07:07

2 楼

string1
|-----------------|
location1 location2

I*A2010-07-11 07:07

3 楼

没看懂
string1怎么move?
"in the intersection for each step" means?

【在 f*********5 的大作中提到】

: string1
: |-----------------|
: location1 location2

f*52010-07-11 07:07

4 楼

string1: abcabcd
string2: abcd
1) abcabcd
abcd
intersection: a and d
2) abcabcd
abcd
intersection: ab/cd
......

【在 I**A 的大作中提到】

: 没看懂
: string1怎么move?
: "in the intersection for each step" means?

d*e2010-07-11 07:07

5 楼

为什么要用笨法子呢？
brute force应该没问题啊。我没具体验证，我想大概应该是这样，
从string_1的第一个char开始循环，比如index是i，和string_2的
第一个char开始比较，index是j，遇到相同，侧两个string的index
都增一，否则看是否得到最长的的substring，然后string_1的index
复位回i，j侧增一，直到j=length(string_2)，然后到下一热循环(i+1)
下面为伪码
int len1 = length(string_1)
int len2 = length(string_2)
int max_len = 0
int left_idx = -1
int right_idx = -1
for i = 0 to len1 - 1
loop
k = i
tmp_max_len = 0
for(j = 0; j < len2 - 1; )
if string_1[k] == string_2[j]
then
k++
j++

【在 I**A 的大作中提到】

: 不许用DP,suffix tree
: http://en.wikipedia.org/wiki/Longest_common_substring_problem
: 笨法子是什么？

I*A2010-07-11 07:07

6 楼

thanks，这个好理解。。
复杂度o(n^2*m) where n is length(s1) and m is length(s2)
如果我已经有了一个算法，就是得到一个string的longest repeated substring,
有没有办法调用这个function来求 longest common substring of two strings?

【在 d**e 的大作中提到】

: 为什么要用笨法子呢？
: brute force应该没问题啊。我没具体验证，我想大概应该是这样，
: 从string_1的第一个char开始循环，比如index是i，和string_2的
: 第一个char开始比较，index是j，遇到相同，侧两个string的index
: 都增一，否则看是否得到最长的的substring，然后string_1的index
: 复位回i，j侧增一，直到j=length(string_2)，然后到下一热循环(i+1)
: 下面为伪码
: int len1 = length(string_1)
: int len2 = length(string_2)
: int max_len = 0