Longest common subsequence 2 - MarisaOJ: Marisa Online Judge

Given two string

$S$ and

$T$ . Find the longest common subsequence (LCS) of

$S$ and

$T$ . ### Input - The first line contains string

$S$ . - The second line contains string

$T$ . ### Output - The length of the LCS. ### Constraints -

$1 \le |S| \le 10^6$ . -

$1 \le |T| \le 5000$ . - Strings contain only lowercase letters. ### Example Input:

$aabaa acba$

Output:

$3$

Exchange labels DP
	Knapsack 4
	Longest common subsequence 2

Topic

Dynamic Programming

Rating

1600

Solution (0)

Solution