Problem Description

We say that a string $S$ contains a string $T$ if $T$ is a subsequence of $S$. That is, we can pick some characters from $S$ and keep their original order to form a new string that is exactly the same as $T$. Given two strings $S$ and $T$, starting from the first character of $T$, what is the maximum number of consecutive characters that are contained in $S$?

Input Format

Two lines, each containing one string. The first line is $S$, and the second line is $T$. Both strings are non-empty and contain only uppercase English letters.

Output Format

Output one integer, the answer.

ABCDEABCD
AABZ

3

Hint

For $20\%$ of the testdata, $1 \le |T| \le |S| \le 20$.

For $40\%$ of the testdata, $1 \le |T| \le |S| \le 100$.

For all testdata, $1 \le |T| \le |S| \le 1000$.

Problem F of Group C in the 2019 Lanqiao Cup National Contest.

Translated by ChatGPT 5