Common Sub-String

Time Limit : 1 sec, Memory Limit : 131072 KB

共通部分文字列

問題

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

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

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

                      ABRACADABRA
                      ECADADABRBCRDARA

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

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

入力

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

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

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

出力

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

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

入出力の例

例1

input.txt

ABRACADABRA
ECADADABRBCRDARA

output.txt

5

例2

input.txt

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

output.txt

0

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. 入力の終わりは EOF で示されます.

Sample Input

ABRACADABRA
ECADADABRBCRDARA
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

Sample Output

5
0

Source: 7th Japanese Olympiad in Informatics , 2008-02-10
http://www.ioi-jp.org/