### Problem

- Given two strings,
`S`

of length`m`

and`T`

of length`n`

- Write an algorithm to find the longest substring of both
`S`

and`T`

### Example

- Input: given two strings "ABABC" and "BABCA". Expected output: "ABC"

### Approach: Bottom Up Dynamic Programming

Optimal substructure:

`L(i, j) = L(i-1, j-1) + 1`

if`S(i-1) == T(j-1)`

with`L(i, j)`

is the length of the common substring at character`S(i)`

and`T(j)`

For the above example, the longest common substring "ABC" has the length at the last common character

`C`

of both`S`

and`T`

,`L(5, 4)`

, equals to the length at the immediate preceding common character`B`

,`L(4, 3)`

, plus 1Bottom-up filling the 2D array

`L[m+1][n+1]`

and keep track the max length and start index of the longest common substring

#### Implementation

```
```

#### Complexity

- Time complexity: O(mn)
- Space complexity: O(mn)