2

我设计了一个算法来找到最长的公共子序列。这些是步骤：

  • 选择第一个字符串中的第一个字母。

  • 在第二个字符串中查找它，如果找到，将该字母添加到 common_subsequence并将其位置存储在 中index，否则将 的长度common_subsequence与 的长度进行比较lcs ，如果更大，则将其值分配给lcs。

  • 返回第一个字符串并选择下一个字母并再次重复上一步，但这一次从第一个index字母开始搜索

  • 重复此过程，直到第一个字符串中没有要选择的字母。最后的值lcs是最长公共子序列。

这是一个例子：
</p> 

X=A, B, C, B, D, A, B‬‬  
‫‪Y=B, D, C, A, B, A‬‬

选择A第一个字符串。在 中
寻找。 现在第二个字符串中有一个，将其附加到. 返回到第一个字符串并选择下一个字母. 这次从 的位置开始在第二个字符串中查找。 有一个之后，所以将 B 附加到. 现在选择第一个字符串中的下一个字母. 第二个字符串中没有旁边。所以将 common_subsequence 的值赋值给，因为它的长度大于. 重复前面的步骤，直到到达第一个字符串的末尾。最终的价值AY
Acommon_subsequence
BBA
BAcommon_subsequence
CCBlcslcslcs是最长公共子序列。

该算法的复杂度为 theta(n*m)。这是我的实现：

第一种算法：

import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

使用哈希表的相同算法：

import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs) 
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed
4

2 回答 2

10

如果您的教授希望您发明自己的 LCS 算法，那么您就完成了。你的算法不是有史以来最优化的算法，但它属于正确的复杂度等级，你清楚地理解它，而且你显然没有从互联网上复制你的实现。您可能希望准备好为您的算法辩护，或讨论替代方案。如果我是你的教授，如果：

  • 你上交了那个程序。
  • 您能够解释为什么没有可能的 O(N) 或 O(N log M) 替代方案。
  • 即使您不知道结果，您也能够参与有关可能具有更好下限（或显着更低的常数等）的其他算法以及时间/空间权衡等的合理讨论提前讨论。

另一方面，如果您的教授希望您选择一种著名的算法并编写自己的实现，您可能希望使用标准的 LP 算法。它是一个标准算法是有原因的——你可能想继续阅读，直到你理解为止。（即使不参加考试，你也是在学习这门课，而不仅仅是为了给教授留下好印象，对吧？）

维基百科有基本实现的伪代码，然后是常见优化的英语描述。我很确定根据该页面上的内容编写自己的 Python 代码不会被视为抄袭，甚至不会被视为微不足道的移植，尤其是如果您可以证明您了解您的代码在做什么、为什么以及为什么这是一个很好的算法。另外，你是用 Python 编写的，它的记忆方式比那篇文章中演示的要好得多，所以如果你理解它是如何工作的，你的代码实际上应该比维基百科给你的要好得多。

无论哪种方式，正如我在评论中建议的那样，我会阅读Bergroth、Hakonen 和 Raita的最长公共子序列算法调查，并在网上搜索类似的论文。

于 2013-01-01T00:45:27.143 回答
-4 
maxLength = 0
foundString = ""
for start in xrange(len(str1)-1):
     for end in xrange(start+1, len(str1)):
        str1Temp = str1[start:end]   
        maxLengthTemp = len(str1Temp)
        if(str2.find(str1Temp)):
             if(maxLengthTemp>maxLength):
                 maxLength = maxLengthTemp
                 foundString = str1Temp

print maxLength
print foundString
于 2012-12-31T23:41:11.263 回答