I**A
发帖数: 2345 | |
f*********5
发帖数: 576 | 2 string1
|-----------------|
location1 location2 |
I**A
发帖数: 2345 | 3 没看懂
string1怎么move?
"in the intersection for each step" means?
【在 f*********5 的大作中提到】
: string1
: |-----------------|
: location1 location2
|
f*********5
发帖数: 576 | 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**e
发帖数: 6098 | 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**A
发帖数: 2345 | 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
|
