How to implement substring algorithm

Question

I am trying to implement an algorithm to take a string of length n and returns all substrings with a length of 2 or greater.

If the user inputs a string e.g "abcd", then the output should be 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']

If you need the list sorted:

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

There is something seriously wrong with your algorithm, because it should only take two loops to do this (one for starting index and one for length of substring). I don't understand what you were trying to do, though, so I can't attempt to fix it.

EDIT: I get it -- you're copying the strings character by character! Are you a C programmer by any chance? =p You don't have to do that sort of thing in Python; it's a higher-level language. If you slice a string (a[1:3]) you will get a substring of it, which you can append to a list or otherwise store. In the above, we iterate first over all indices up to the end of the string (minus one because "d" is not a valid substring) and then over all lengths of substring that will 'fit'. This yields all possible substrings; we can use list comprehension notation to make a list of them very easily.

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

If you want to output the results from shortest to longest

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

To store the results in a list

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

Here is a bug fixed version of your code to compare, but there are better ways to write it here

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

In python 2.6 they added some cool functions that makes this quite easy:

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)

Note that substrings() is a generator (see the yield statement), which is more memory efficient, but if you really need a list, you can say mylist = list(substrings('foo'))

I've also added an argument to substrings if you ever want to generate substrings of some other length.

Answer 7

A concise, recursive version, for good measure:

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)