Как написать функцию для поиска позиций подстроки в большей строке без использования функции «найти»?

Я только недавно начал использовать python, и я очень плохо знаком с python и программированием в целом, и я учусь в классе, где нам дали задание найти функцию в Python, которая принимает две строки последовательности ДНК (скажем, string1 и string2 ) в качестве входных данных и возвращает список позиций, в которых строка2 присутствует в качестве подстроки строки1. И поскольку предполагается, что мы знакомимся с тем, как работает программирование, мы не можем использовать встроенную функцию «найти». Я действительно смущен тем, как даже начать эту проблему. Но это то, что у меня есть до сих пор:

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]


python list string substring linear-search
person Mallory Schmidt    schedule 09.02.2019    source источник
comment
Поскольку это задание, никто не собирается давать вам ответ. В частности, сообщите об ошибке, которую вы получаете, и кто-то может помочь вам устранить ошибку.   -  person floydn    schedule 10.02.2019

Ответы (1)


arrow_upward
1
arrow_downward

К сожалению, это не может быть [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]
person Igor Dragushhak    schedule 09.02.2019
comment
Большое спасибо! Это было очень полезно! - person Mallory Schmidt; 10.02.2019