算法探讨,求公共子串问题

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

1^# shaohui 发表于 2006-06-15 00:50

算法探讨,求公共子串问题

设计一个算法，求两个字符串s1,s2的最长公共子字符串的长度．
用Python 写了个简单的实现

[Copy to clipboard] [ - ]

CODE:

def commstr(long,short) :
if short in long :
return len(short)
return max(commstr(long,short[:-1]),commstr(long,short[1:]))

print commstr('shaohui','uihoahs')

如果要改成求出这个公共子字符串也很容易

[Copy to clipboard] [ - ]

CODE:

def commstr(long,short) :
if short in long :
return short
s1 = commstr(long,short[:-1])
s2 = commstr(long,short[1:])
if len(s1) > len(s2) :
return s1
else :
return s2

print commstr('shaohui','edward')

这是我的算法,我期待着有更好的算法出现，希望大家能够共同探讨

下面这篇文章详细说明了我的改进算法,不知道大家觉得如何?

http://blog.csdn.net/shaohui/archive/2006/06/09/784577.aspx

guotie

UID: 37694
帖子: 58
积分: 133
在线时间: 4 小时

2^# guotie 发表于 2006-06-15 10:10

递归，递归，又见递归；

stone.zh

UID: 39884
帖子: 157
积分: 361
在线时间: 1 天 9 小时

3^# stone.zh 发表于 2006-06-15 22:38

写得很精练, 还可以稍稍修饰一下:

def commstr(long,short) :
if(len(long) < len(short)):
long, short = short, long
....

另外, 这样的算法有好多重复计算。

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

4^# shaohui 发表于 2006-06-16 00:44

QUOTE:

if(len(long) < len(short)):
long, short = short, long

stone.zh不愧是老手哦

不过这里是不用交换long和short的，即使是len(long) < len(short)按照这个算法也是可以正确计算出来的

jkit

UID: 1841
帖子: 174
积分: 400
在线时间: 1 天 17 小时

5^# jkit 发表于 2006-06-16 11:34

这种算法和目标字符串的长度以及范围等密切相关。
如果两个字符串很长，简单的算法几乎不可能胜任。
如果两个字符串很短：
一：而且非常相像，那么楼主的算法还算过得去。
二：如果不相像，例如随即产生的字符，那么是可以优化的
优化方案：L较长字符串，S较短字符串
1：判断S中是否含有L中不存在的字符，如果有，那么分段，此时S的子串列表SS中的字符全部在L中存在
2：判断L中是否含有S中不存在的字符，如果有，那么分段，此时L的子串列表LL中的字符全部在S中存在
3：求子串列表LL和子串列表SS的最大公共串
3.1：依次取出LL中的元素，如果其长度小于当前最大公共串长度则忽略
3.2：依次取出SS中的元素，如果其长度小于当前最大公共串长度则忽略
3.3：用楼主的算法求此两个子串的最大公共串，如果其长度大于当前最大公共串，则设为当前最大公共串

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

6^# shaohui 发表于 2006-06-21 18:04

对于任意长度分别为n,m
jkit的方法确实是可行的,时间复杂度为O(n*m)

实际上，的字符串可以在O(n*m)的时间内求出它们的公共子串
当然用我说的方法肯定是不行的,因为如果让n=m,那么我所用的方法的复杂度为O(n*n*n*n)

Orpherus

UID: 10333
帖子: 107
积分: 246
在线时间: 15 小时

7^# Orpherus 发表于 2006-06-22 06:53

动态规划算法

或者参考这个更加高级的
An O(ND) Difference Algorithm and Its Variations*
EUGENE W. MYERS
Department of Computer Science, University of Arizona, Tucson, AZ 85721, U.S.A.

shaohui

UID: 33184
帖子: 1
积分: 2
在线时间: 10 分钟

8^# shaohui 发表于 2006-06-22 17:41

jkit说对了,当规模比较大大的时候确实太费时间了

[Copy to clipboard] [ - ]

CODE:

def commstr(long,short) :
if short in long :
return short
s1 = commstr(long,short[:-1])
s2 = commstr(long,short[1:])
if len(s1) > len(s2) :
return s1
else :
return s2

print commstr('Require the Sub String in the parent string is continous','Who will be the next Morse?')

运行这个程序的时候,我都要睡着了

pigflw

UID: 11266
帖子: 138
积分: 317
在线时间: 1 天 2 小时

9^# pigflw 发表于 2006-06-23 09:56

那位老大有时间把kmp算法实现下