Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
百人一首には「わたのはら」で始まる歌が2首あり、6文字目を聞いて初めて取る札を確定できます。このように、「最初から q 文字目までが百人一首の他のどの歌とも共通しない」を満たす最小の q が p であるとき、その歌は「 p 字決まりである」と言います。例えば、「わたのはら」で始まる2首は6字決まりです。
数学家の高橋くんは、 p 字決まりの概念を拡張した真・ p 字決まりを考えました。ある歌 S が真・ p 字決まりであるとは、以下の条件を満たす最小の q が p であることを指します。
- S のどの長さ q の部分列も、歌集の他の歌の部分列でない
この真・ p 字決まりをさっそく使いたくなった高橋君は、青木さんの歌集「一人二首」の歌で調べることにしました。一人二首は、青木さんの詠んだ2つの歌 S,\ T のみで構成されています。高橋くんに代わって、和歌 S が「一人二首」において真・何字決まりであるか求めなさい。2つの和歌は同一ではないことが保証されます。
部分列とは
ある文字列 s の部分列は、 s の中から連続するとは限らない0個以上の文字を選択して元の順に並べた文字列のことを指します。例えば、rhhan
やirohachan
、空文字列はirohachan
の部分列ですが、takahashikun
やnahcahori
はそうではありません。
制約
- S と T は英小文字のみで構成される文字列
- 1 \leq |S|=|T| \leq 5000
- S \neq T
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
和歌 S が真・p 字決まりであるとき、p を1行で出力せよ。
入力例 1
abbcd abccd
出力例 1
5
入力例 2
watanoharayasosimakaketekogiidenuto watanoharakogiidetemirebahisakatano
出力例 2
20