string substrings

🏠

[]

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.