Генерация всех покрывающих подстрок строки

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 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']

Answer 2

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