Mô tả và yêu cầu

2014 Bài C - Xâu con chung dài nh ấ t

X âu ký tự S đ ượ c g ọ i l à xâu con của xâu ký tự T n ế u ta có th ể xoá đi mộ t số ký tự trong xâu T đ ể
nh ận đ ượ c xâu S . Gọ i LC S (X , Y ) l à độ dài xâu con chung dài nh ấ t của X và Y .

Y êu c ầu: C ho n xâu S _1, S _2, ... ,S _n. H ãy tính G = max{ LC S (S _i , S _j ) } vớ i tất cả các ch ỉ số i
khác j thỏ a mãn 1 <= i , j <= n.

In p u t

D ữ l iệu vào g ồ m nhi ều b ộ dữ l iệu tươ ng ứng vớ i nhiều test. D òng đ ầu ti ên ch ứa số nguyên K l à
số bộ dữ l iệu. Ti ếp theo l à K (K ≤100) dòng, mỗ i dòng l à mộ t bộ d ữ l iệu có cấ u trúc nh ư sau:

- D òng đ ầ u ti ên của nhóm ch ứa số nguyên.

- D òng tiế p theo, mỗ i dòng ch ứa mộ t xâu ký tự đ ộ dài không vượ t quá 30, ch ỉ gồ m các ký tự i n
hoa.

Ou tp u t

Vớ i mỗ i bộ dữ l iệu ghi ra trên mộ t dòng, mỗ i dòng ghi ra mộ t số nguyên l à câu trả l ờ i tương ứng
vớ i bộ dữ l iệu trong d ữ l iệu vào.

E x a mp le

I nput:
2
2
A LI CE
B OB
2
A B CB
B CA B

Dữ liệu ra

0
3