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