20011. Fast the Length of the Longest Common Subsequence

I'm a slow walker, but I never walk backwards.

題目描述

給兩個字串 $X, \; Y$,在兩個字串中都有出現且最長的子序列 (subsequence),就是最長共同子字串 。

輸入格式

有多組測資,每組測資有兩行字串 $X, \; Y$,$X, \; Y$ 只由 A T C G 四個字母構成。

  • $1 \le \vert X\vert , \vert Y\vert \le 60000$

輸出格式

針對每一組測資,輸出一行 $X, \; Y$ 的最長共同子字串長度。

範例輸入

TCA
GTA
TGGAC
TATCT

範例輸出

2
3

測資組

  • 1.in 10000 組長度介於 1 到 100
  • 2.in 1000 組長度介於 200 到 500
  • 3.in 300 組長度介於 1000 到 2000
  • 4.in 50 組長度介於 2000 到 5000
  • 5.in 10 組長度介於 10000 到 60000

Discussion