罗莎琳德解决方案固定:共享图案

Question

我知道罗莎琳德挑战有解决方案，但我不希望它们破坏乐趣。我以为我找到了"寻找共同主题"的解决方案，但我的答案总是错误的。

问题是关于在给定工作表中查找最长的公共子字符串，该子字符串由以">"开头的行和下一行组成，直到另一行以">"开头组成序列。 下面是它的外观：

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

有一百个DNA片段，你要找到最长的共同亚序列。这是我的方法：

rosa = open("rosalind_lcsm.txt","r")
oku = rosa.readlines()
strs=[]
for line in oku:
if line.startswith(">"):
strs.append("kiko")
else:
strs.append(line)
rosa.close()
strs = strs[1:]
joint = "".join(strs)
joint_s = joint.split("kiko")
theOne = joint_s[0]
rest = joint_s[1:]
start=0
end=1
matches=[]
while end < len(theOne):
end+=1
while all(theOne[start:end] in seq for seq in rest):
end+=1
else:
matches.append(theOne[start:end-1])
end+=1
start=end-1
print(max(matches, key=len))

我的策略是：阅读文件，将其拆分为序列，选择第一个序列并将其公共部分与其他部分进行比较。我正在检查至少 2 个匹配项，因为序列是由 ATGC 组成的，肯定会发生 1 个匹配项。它从一个角色开始，并不断将其扩展 1 个字符，直到匹配被打破。然后，它获取最后一个匹配位并附加到列表中。然后从停止的位置重新启动。

我的解决方案给出了答案，但它不是正确的答案，我无法发现代码中的误导性部分。有人可以尝试理解我的方法并给我修复它的建议吗？

Answer 1

我不会说 python，但我认为您通过执行start=end-1跳过了可能的匹配。您可能需要执行start=start+1。

例如，假设您有以下字符串：

加特卡 加格卡特卡

您的算法将首先找到 GA 作为公共子字符串，然后从第三个字符继续查找。但这样你就错过了真正最长的公共子字符串 ATCAA。

编辑：显然您还需要与start一起重新初始化end。您可以将其设置为start+1以始终像您所做的那样从两个字母的字符串开始查找，或者您可以通过从到目前为止找到的最长匹配项的长度开始优化代码。