Как реализовать алгоритм подстроки

Question

Я пытаюсь реализовать алгоритм, чтобы взять строку длиной n и возвращает все подстроки длиной 2 или больше.

Если пользователь вводит строку, например, «abcd», то вывод должен быть ab, bc, cd, abc, bcd, abcd.

a=input("Ente the input") 
list=[] 
com="" 
for k in range(2,len(a)+1): 
    for x in range(k,len(a)+1): 
     com="" 
     for j in range(x-k,k); 
      com=com+a[j] 
     print com 
     list1.append(com) 

print list1 

Answer 1

>>> [ a[ index : index + length ] for index in range(len(a) - 1) for length in range(2, len(a) - index + 1) ] 
['ab', 'abc', 'abcd', 'bc', 'bcd', 'cd'] 

Если вам нужен список, отсортированный:

>>> sorted([ a[ index : index + length ] for index in range(len(a) - 1) for length in range(2, len(a) - index + 1) ], key = len) 
['ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Существует что-то серьезно не так с вашим алгоритмом, потому что он должен взять только две петли, чтобы сделать это (один для исходного индекса и один для длины подстроки). Однако я не понимаю, что вы пытались сделать, поэтому я не могу его исправить.

EDIT: Я понимаю - вы копируете символ символов персонажем! Вы случайно программируете на C? = p Вам не нужно делать подобные вещи в Python; это язык более высокого уровня. Если вы нарезаете строку (a[1:3]), вы получите подстроку, которую вы можете добавить в список или сохранить в другом месте. В приведенном выше примере мы сначала итерации по всем индексам до конца строки (минус один, потому что «d» не является допустимой подстрокой), а затем по всем длинам подстроки, которые будут «соответствовать». Это дает все возможные подстроки; мы можем использовать нотацию списка, чтобы составить список из них очень легко.

Answer 2

minlength = 2 
def sub(string): 
    return [string[start:start+length] 
     for length in xrange(minlength, len(string) + 1) 
      for start in xrange(len(string) - length + 1) ] 
print sub('abcd') 
['ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Answer 3

from itertools import combinations 
map(lambda i: a[i[0]:i[1]+1],combinations(range(len(a)),2)) 

Answer 4

Если вы хотите выводить результаты от коротких до самой длинной

>>> s="abcd" 
>>> for substrlength in range(2, len(s)+1): 
...  for start in range(len(s)+1-substrlength): 
...   print s[start:start+substrlength] 
... 
ab 
bc 
cd 
abc 
bcd 
abcd 

Чтобы сохранить результаты в списке

>>> s="abcd" 
>>> resultlist=[] 
>>> for substrlength in range(2, len(s)+1): 
...  for start in range(len(s)+1-substrlength): 
...   resultlist.append(s[start:start+substrlength]) 
... 
>>> print resultlist 
['ab', 'bc', 'cd', 'abc', 'bcd', 'abcd'] 

Answer 5

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

a=raw_input("Enter the input") 
list1=[] 
com="" 
for k in range(2,len(a)+1): 
    for x in range(k,len(a)+1): 
     com="" 
     for j in range(x-k,x): 
      com=com+a[j] 
     print com 
     list1.append(com) 

print list1 

Answer 6

В Python 2.6 они добавили некоторые интересные функции, что делает это довольно легко:

from itertools import combinations 

def substrings(text, length=2): 
    textlen = len(text) 
    for low, hi in combinations(range(textlen), 2): 
     if hi-low >= length: 
      yield text[low:hi] 

s = raw_input("Enter the input: ") 
for substr in substrings(s): 
    print len(substr), repr(substr) 

Обратите внимание, что substrings() является генератором (см yield заявление), которое больше памяти эффективным, но если вам действительно нужно список, вы можете сказать mylist = list(substrings('foo'))

Я также добавил аргумент подстрокам, если вы когда-либо захотите создать подстроки какой-либо другой длины.

Answer 7

Сжатая, рекурсивная версия, для хорошей меры:

def substr(s, min_len): 
    if len(s) < min_len: 
     return [] 
    return [s[i:i+min_len] for i in range(len(s) - min_len + 1)] + substr(s, min_len + 1)