How to implement substring algorithm [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 12 years ago.

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

---

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

---

from  itertools import combinations
map(lambda i: a[i[0]:i[1]+1],combinations(range(len(a)),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']

---

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

---

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

---

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.

---

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)