Базовое индексирование повторений подстроки в строке (python)

Question

Я работаю над обучением основам программирования.
Один простой проект - найти индекс повторений подстроки в строке. Так, например, в строке «abcdefdef» и подстроке «def» я хотел бы, чтобы выходные данные были 3 и 6. У меня есть некоторый написанный код, но я не получаю ответы, которые я хочу. Вот что я написал

---

Примечание : я знаю, что может быть более простой способ получения результата, используя встроенные функции / пакеты языка, такие как регулярные выражения. Я также знаю, что мой подход, вероятно, не оптимальный алгоритм. Тем не менее, в настоящее время я только ищу совет по исправлению следующей логики, а не использую более идиоматические подходы.

import string

def MIT(String, substring): # "String" is the main string I'm searching within
    String_list = list(String)
    substring_list = list(substring)
    i = 0
    j = 0
    counter = 0
    results = []
    while i < (len(String)-1):
        if [j] == [i]:
            j = j + 1
            i = i + 1
            counter  = counter + 1
            if counter == len(substring):
                results.append([i - len(substring)+1])
                counter = 0
                j = 0
                i = i+1
        else:
            counter = 0
            j = 0
            i = i+1
    print results
    return

Моя аргументация такова. Я превращаю строку и подстроку в список. Это позволяет индексировать каждую букву в строке. Я установил i и j = 0 - это будут мои первые значения в индексе String и substring соответственно. У меня также есть новая переменная counter, которую я установил = 0. По сути, я использую счетчик, чтобы подсчитать, сколько раз буква в позиции [i] равна элементу в позиции [j]. Если counter равен длине подстроки, то я знаю, что [i - len (substring) + 1] - это позиция, с которой начинается моя подстрока, поэтому я добавляю ее в список с именем results. Затем я сбрасываю счетчик и j и продолжаю поиск дополнительных подстрок.

Я знаю, что код неудобен, но я подумал, что все еще смогу получить ответ. Вместо этого я получаю:

>>> MIT("abcdefghi", "def")
[[3]]
>>> MIT("abcdefghi", "efg")
[[3]]
>>> MIT("abcdefghi", "b")
[[1]]
>>> MIT("abcdefghi", "k")
[[1]]

Есть мысли?

Answer 1

Сначала я добавил несколько комментариев к вашему коду, чтобы дать несколько советов

import string

def MIT(String, substring): 
    String_list = list(String)  # this doesn't need to be done; you can index strings
    substring_list = list(substring)
    i = 0
    j = 0
    counter = 0
    results = []
    while i < (len(String)-1):   
        if [j] == [i]:   # here you're comparing two, one-item lists. you must do substring[j] and substring[i]
            j = j + 1
            i = i + 1
            counter  = counter + 1
            if counter == len(substring):
                results.append([i - len(substring)+1]) # remove the brackets; append doesn't require them
                counter = 0
                j = 0
                i = i+1 # remove this 
        else:
            counter = 0
            j = 0
            i = i+1
print results
return

Вот как бы я это сделал, не используя встроенные библиотеки и прочее:

def MIT(fullstring, substring):
    results = []
    sub_len = len(substring)
    for i in range(len(fullstring)):  # range returns a list of values from 0 to (len(fullstring) - 1)
        if fullstring[i:i+sub_len] == substring: # this is slice notation; it means take characters i up to (but not including) i + the length of th substring
            results.append(i)
    return results

Answer 2

Основная / основная проблема заключается в следующем:

• для сравнения используйте: if String[i] == substring[j]
• Вы увеличиваете i дважды, когда нашли совпадение, удалите второеинкремент.
• цикл должен идти до while i < len(String):

и, конечно, он не найдет совпадающие совпадения (например: MIT("aaa", "aa"))

Естьнекоторые незначительные «проблемы», это не совсем питонно, нет необходимости создавать списки, инкремент более понятен, если написано i += 1, полезная функция должна возвращать значения, а не печатать их и т. д. *

ЕслиВы хотите правильный и быстрый код, проверьте книгу классических алгоритмов: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844.В ней есть целая глава, посвященная поиску строк.

Если вы хотите получить питонное решение без полной реализации, проверьте другие ответы.

Answer 3

Модуль регулярных выражений (re) гораздо больше подходит для этой задачи.

Полезная ссылка: http://docs.python.org/howto/regex.html

Также: http://docs.python.org/library/re.html

РЕДАКТИРОВАТЬ: Aболее «ручным» способом может быть использование нарезки

s = len(String)
l = len(substring)
for i in range(s-l+1):
    if String[i:i+l] == substring:
        pass #add to results or whatever

Answer 4

Для нахождения позиции подстроки в строке этот алгоритм будет делать:

def posnof_substring(string,sub_string):
l=len(sub_string)
for i in range(len(string)-len(sub_string)+1):
    if(string[i:i+len(sub_string)] == sub_string ):      
        posn=i+1
return posn           

Я сам проверил этот алгоритм, и он работал!

Answer 5

Мне неясно, хотите ли вы изучить некоторые хорошие алгоритмы поиска строк или простой способ сделать это в Python.Если это последнее, то string.find ваш друг.Что-то вроде

def find_all_indexes(needle, haystack):
    """Find the index for the beginning of each occurrence of ``needle`` in ``haystack``. Overlaps are allowed."""
    indexes = []
    last_index = haystack.find(needle)
    while -1 != last_index:
        indexes.append(last_index)
        last_index = haystack.find(needle, last_index + 1)
    return indexes


if __name__ == '__main__':
    print find_all_indexes('is', 'This is my string.')

Хотя это довольно наивный подход, он должен быть легко понятен.

Если вы ищете что-то, что использует еще меньше стандартной библиотеки (и будет на самом деленаучить вас довольно распространенному алгоритму, используемому при реализации библиотек), вы можете попробовать реализовать алгоритм поиска строк Бойера-Мура .