Longest Common Subsequence (LCS)

A005 Time Limit: 1.000 s Memory Limit: 64 MB
Submissions

Given two sequences $S$ and $T$, find the length of the longest common subsequence.

A subsequence is a string that can be derived from another string by deleting some or no symbols without changing the order of the remaining symbols.
Input

Two lines, corresponding to $S$ and $T$ respectively.

Output

The length of the longest common subsequence (LCS).

Constraints
  • $|S|, |T| \le 10^3$
  • $S, T$ only consists of lowercase alphabet characters.

Sample Test Cases

Input Output
acaatcc
agcatgc		 5
The LCS is acatc.
Click to copy.
Scoring: Per Subtask
Authored by s17f18