python - 如何编写一个函数来查找较大字符串中子字符串的位置而不使用 'find' 函数？

Question

我最近刚刚开始使用 python，我对 python 和一般编码非常陌生，我在一个类(class)中，我们被要求在 Python 中找到一个函数，该函数需要两个 DNA 序列字符串(比如string1 和 string2) 作为输入，并返回 string2 作为 string1 的子字符串出现的位置列表。由于我们应该熟悉编码的工作原理，因此我们不能使用“查找”内置函数。我真的很困惑如何开始这个问题。但这是我到目前为止所拥有的:

def linear(seq, sub):
    positions = [0]
    for i in range(len(sub)):
        if seq[i:i+len(sub)] == sub:
             positions[0]+=1
    return( positions )

当我输入这个时，我收到一个错误，但我应该列出子字符串出现的位置列表。如果有人可以指导我应该朝哪个方向前进，那将非常有帮助。

举个例子，如果序列是“ATTCCATGGACCTAGTCAT”并且我要查找的子字符串是“CAT”，那么输出应该是[5,17]

Answer 1

不幸的是，它不能是[5,17]，因为Python中的索引从0开始，它应该是[4,16]。您可以使用 for 循环遍历索引，直到最后一个索引减去子字符串的长度加上 1 以避免超出范围。然后检查字符串的切片是否为当前索引，直到当前索引加上子字符串的长度(如果是 'CAT' 那么您将得到 长度的每个切片>3 的字符串)，等于子字符串。如果是，则将索引附加到索引列表中。

def find(st,sub):
    list_of_pos=[]
    for i in range(len(st)-len(sub)+1):
        if st[i:i+len(sub)]==sub:
            list_of_pos.append(i)
    return list_of_pos

如果使用列表理解，可以使其更加紧凑:

def find(st,sub):
    return [i for i in range(len(st)-len(sub)+1) if st[i:i+len(sub)]==sub]