Description

Given two strings S and T, where the length of S is guaranteed to be no less than that of T. The question asks for the minimum number of characters that need to be modified in S so that T becomes a subsequence of S.

Input Format

The input consists of two lines:

The first line is string S, and the second line is string T.

It is guaranteed that the length of S is no less than that of T, and the length of S ranges between 10 and 1000.

Output Format

The minimum number of characters to be modified in S.

```input1 ABCDABCD AABCX

```output1
1

ABCDABCD
XAAD

2

XBBBBBAC
ACC

2

Hint

Example 1: Change S: ABCDABCD to ABCDABCX (I understand that a subsequence means S contains all elements of T in order, not necessarily consecutively) (Not sure if the styling will remain, bolded parts are T, underlined parts are modifications)

Example 2:

Original: ABCDABCD

Modified: XACDABCD

Example 3:

Original: XBBBBBAC

Modified: ABBBBBCC

(In Example 3, A can replace any of the preceding B's or X. For example: XABBBBCC)

Source

2019 10th Lanqiao Cup C/C++ Group B National Finals Real Questions