Базовые индексирующие рекурсии подстроки в строке (python)

Я работаю над преподаванием базового программирования.
Один простой проект – найти индекс рекуррентности подстроки внутри строки. Так, например, в строке «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 и подстроки, соответственно. У меня также есть новая переменная, счетчик, которую я установил = 0. В принципе, я использую счетчик, чтобы подсчитать, сколько раз буква в позиции [i] равна элементу в позиции [j]. Если счетчик равен длине подстроки, то я знаю, что [i-len (substring) + 1] – это позиция, в которой начинается моя подстрока, поэтому я добавляю ее в список, называемый результатами. Затем я сбрасываю счетчик и j и продолжаю поиск дополнительных подстрок.

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

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

Есть предположения?

5 Solutions collect form web for “Базовые индексирующие рекурсии подстроки в строке (python)”

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

Хорошая ссылка: http://docs.python.org/howto/regex.html

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

EDIT: более «ручным» способом может быть использование нарезки

 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 

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

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

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

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

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

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

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

 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 

Я не понимаю, хотите ли вы изучить хорошие алгоритмы поиска строк или простой способ сделать это в 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.') 

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

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

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

 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 

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

  • Список индексов повторяющихся значений в списке с помощью Python
  • Попытка подсчета слов в строке
  • Python: для каждого элемента списка применяется функция в списке
  • Словарь Python содержит список как значение - как обновить?
  • Мутирующий список в python
  • Python: Итерируя списки с разным количеством измерений, существует общий способ?
  • Оптимизация расчета расстояния Python при учете периодических граничных условий
  • Python Самый простой способ суммировать список Пересечение списка кортежей
  • Python - лучший язык программирования в мире.