Problem
- Given two strings,
S
of lengthm
andT
of lengthn
- Write an algorithm to find the longest substring of both
S
andT
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
ifS(i-1) == T(j-1)
withL(i, j)
is the length of the common substring at characterS(i)
andT(j)
For the above example, the longest common substring "ABC" has the length at the last common character
C
of bothS
andT
,L(5, 4)
, equals to the length at the immediate preceding common characterB
,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)