# string substrings

Go Back home

[]

The string:

1 A = 'abcd'


Has substrings:

 1 a
2 ab
3 abc
4 abcd
5
6 b
7 bc
8 bcd
9
10 c
11 cd
12
13 d


Generating substrings is costly, in fact the time complexity is O(n^2). However it can be very useful knowing how to do so, especially when working on a brute force algorithm for string matching problems.

1 s = 'abcd'
2 for i in range(len(s)):
3   print('')
4   for j in range(i, len(s)):
5     print(s[i:j+1])


It can also be useful generating them in reverse order:

1 s = 'abcd'
2 for i in range(1, len(s)+1):
3   print('')
4   for j in range(i):
5     print(s[j:i])


Output:

 1 a
2
3 ab
4 b
5
6 abc
7 bc
8 c
9
10 abcd
11 bcd
12 cd
13 d


## Pythonic

1 s = 'abcd'
2 [s[i:j+1] for i in range(len(s)) for j in range(i, len(s))]


## Complexity

The complexity is f(n) = n*(n+2)/2 which is O(n^2)

Please note that strings and lists are treated very similarly in python for many intents and purposes, so when discussing array subarrays the exact same technique would apply.