A - わたのはら /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300

問題文

百人一首には「わたのはら」で始まる歌が2首あり、6文字目を聞いて初めて取る札を確定できます。このように、「最初から q 文字目までが百人一首の他のどの歌とも共通しない」を満たす最小の qp であるとき、その歌は「 p 字決まりである」と言います。例えば、「わたのはら」で始まる2首は6字決まりです。

数学家の高橋くんは、 p 字決まりの概念を拡張した真・ p 字決まりを考えました。ある歌 S が真・ p 字決まりであるとは、以下の条件を満たす最小の qp であることを指します。

  • S のどの長さ q の部分列も、歌集の他の歌の部分列でない

この真・ p 字決まりをさっそく使いたくなった高橋君は、青木さんの歌集「一人二首」の歌で調べることにしました。一人二首は、青木さんの詠んだ2つの歌 S,\ T のみで構成されています。高橋くんに代わって、和歌 S が「一人二首」において真・何字決まりであるか求めなさい。2つの和歌は同一ではないことが保証されます。

部分列とは

ある文字列 s部分列は、 s の中から連続するとは限らない0個以上の文字を選択して元の順に並べた文字列のことを指します。例えば、rhhanirohachan、空文字列はirohachanの部分列ですが、takahashikunnahcahoriはそうではありません。

制約

  • ST は英小文字のみで構成される文字列
  • 1 \leq |S|=|T| \leq 5000
  • S \neq T

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

和歌 S が真・p 字決まりであるとき、p1行で出力せよ。


入力例 1

abbcd
abccd

出力例 1

5

入力例 2

watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano

出力例 2

20

解説

解説