B - 共通部分文字列 Editorial /

Time Limit: 1.5 sec / Memory Limit: 64 MiB

配点: 20

2 個の文字列が与えられたとき,両方の文字列に含まれる文字列のうち最も長いものを探し,その長さを答えるプログラムを作成せよ.

ここで,文字列 s が文字列 t に含まれるとは,t の中に s が連続して現れることをいう. 空文字列,すなわち長さ 0 の文字列は,どんな文字列にも含まれる. 例えば,文字列 ABRACADABRA には次の文字列が含まれる: ABRARACDACADABRAABRACADABRA,空文字列など. 一方,文字列 ABRACADABRA には次の文字列は含まれない: ABRCRAABAK など.

例 1: 文字列として ABRACADABRAECADADABRBCRDARA が与えられた場合,両方に含まれる文字列には CACADAADABR や空文字列などがある. そのうち最も長いのは ADABR であり,その長さは 5 である. 2 個の文字列の中に含まれる ADABR の位置を図 2-1 に示す.

図 2-1 例 1 の文字列の中に現れる \texttt{ADABR} の位置

例 2: 文字列として UPWJCIRUCAXIIRGLSBQNYBSBZDFNEV が与えられた場合,両方に含まれる文字列は空文字列のみであり,その長さは 0 である.


入力

入力ファイルのファイル名は input.txt である.

入力は 2 行からなり,1 行目に 1 個目の文字列が,2 行目に 2 個目の文字列が与えられる. 文字列は英大文字からなり,各々の文字列の長さは 1 以上 4000 以下である.

採点用データのうち,配点の 30 %分については,各々の文字列の長さは 1 以上 50 以下である.

出力

出力ファイルのファイル名は output.txt である.

output.txt は,与えられた 2 個の文字列の両方に含まれる文字列のうち最も長 いものの長さだけを含む 1 行からなる.


入力例 1

ABRACADABRA
ECADADABRBCRDARA

出力例 1

5

入力例 2

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

出力例 2

0

Source Name

JOI 2007/2008 本選 問題2