AlgorithmDynamic Programming

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 1

  • Bottom-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)
AlgorithmDynamic Programming