Codeforces ラウンド #244 (ディビジョン 2)D(String DP)_html/css_WEB-ITnose

D. マッチ＆キャッチ

テストごとの制限時間

1 秒

テストごとのメモリ制限

512 メガバイト

入力

標準入力

出力

標準出力

警察本部はさまざまな周波数レベルで信号を監視します。彼らは、2 つの異なる周波数から、疑わしくエンコードされた 2 つの文字列 s1 と s2 を信号として取得しました。彼らは、これら 2 つの文字列が 2 人の異なる犯罪者からのものであると疑い、何らかの邪悪な任務を計画しています。

現在、彼らはこれら 2 つの文字列間の最小長の共通部分文字列を見つけようとしています。部分文字列は、最初の文字列で 1 回だけ出現する必要があり、2 番目の文字列でも 1 回だけ出現する必要があります。

2 つの文字列 s1 と s2 が小文字のラテン文字で構成されている場合、両方の s1 の（長さによる）最小の共通部分文字列 p を見つけます。および s2。ここで、pi は s1 と s2 にある一意の部分文字列です。部分文字列の正式な定義と一意性については、注を参照してください。

入力

入力の最初の行には s1 が含まれ、2 行目には s2 (1?≤?|s1|,?|s2|?≤?5000) が含まれています。どちらの文字列もラテン文字の小文字で構成されています。

出力

s1 と s2 の最小の共通の一意の部分文字列の長さを出力します。 s1 と s2 に共通の一意の部分文字列がない場合は、-1 を出力します。

サンプル テスト

入力

applepepperoni

出力

input

出力

入力

loverdriver

出力

bidhanroy

入力

-1

出力

注

文字列があると想像してくださいa?=?a1a2a3...a|a|、ここで |a| は文字列 a の長さで、ai は文字列の i 番目の文字です。

string alal?+?1al?+?2...ar(1?≤?l?≤?r?≤?| a|) 文字列 a.

の部分文字列 [l,?r]

部分文字列 [l,?r] は、l1?≠?l のような l1,?r1 のペアがない場合に限り、a 内で一意になります。部分文字列 [l1,?r1] は、a の部分文字列 [l,?r] と等しいです。 i は開始点、s2 中以j は開始点の最長期一致子串

dp2[i][j] は、s1 中以i が開始点、s1 中以j が開始点の最長期一致子串を示します。串

その後枚s1 の每个位置 i、s2 ですべてと i の位置一致する串

s1 ですべて（除了i位置）i 位置と一致する列

然后分情况讨论即可~