Générer toutes les sous-chaînes de recouvrement d'une chaîne

Question

Comment faites-vous ce qui suit: à l'aide d'une chaîne de caractères, générez toutes les manières possibles d'analyser cette chaîne en sous-chaînes (le temps est important, l'espace ne vous intéresse pas). Par exemple, étant donné la chaîne ABCD, je dois générer:

ABCD 

A BCD 

A BC D 

A B CD 

AB CD 

AB C D 

ABC D 

A B C D 

probablement une solution récursive, mais je ne peux pas tout à fait le faire fonctionner.

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

Une autre solution en Python, sans récursion:

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

afin que

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