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$, find the minimum number of characters in $S$ that need to be modified so that $S$ contains $T$.

Input Format

Input consists of two lines, each containing a string. The string on the first line is $S$, and the string on the second line is $T$. Both strings are non-empty and contain only uppercase English letters.

Output Format

Output one integer, which is the answer.

ABCDEABCD
XAABZ

3

Hint

For $20\%$ of the test cases, $1 \leq |T| \leq |S| \leq 20$.

For $40\%$ of the test cases, $1 \leq |T| \leq |S| \leq 100$.

For all test cases, $1 \leq |T| \leq |S| \leq 1000$.

Lanqiao Cup 2019 National Contest, Group B, Problem F.

Translated by ChatGPT 5