Создание всех подстрок покрытия строки

Question

Как вы: задаете строку, генерируете все возможные способы синтаксического анализа этой строки в подстроках (время важно, космос не заботится). Например, если строка ABCD, мне нужно создать:

ABCD 

A BCD 

A BC D 

A B CD 

AB CD 

AB C D 

ABC D 

A B C D 

Возможно рекурсивное решение, но я совсем не могу получить его на работу.

Answer 1

Python:

def splitstring(s): 
    result = [s] 
    for i in range(1, len(s)): 
    result.extend('%s %s' % (s[:i], x) for x in splitstring(s[i:])) 
    return result 

Answer 2

Другое решение в Python, без рекурсии:

def substrings(s): 
    for k in xrange(1, len(s)+1): 
     for i in xrange(len(s)-k+1): 
      yield s[i:i+k] 

так что

>>> print list(substrings("ABCD")) 
['A', 'B', 'C', 'D', 'AB', 'BC', 'CD', 'ABC', 'BCD', 'ABCD']