Binbin's string
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

One day, Binbin picked up a string S at the beach, but she likes string T. Therefore, she needs to take some action on the string to make the string S become the string T. She has two kind of operation to modify the string. The first operation is to delete Y characters after the X-th position of the string (including the X-th character).The second operation is to insert the string A after the X-th position of the string, if you want to insert it at the beginning, just insert A after the 0th position.

For example, there is a string S="iwannaac", choose the first operation, delete 2 characters after the 7th character, it will become "iwanna"; then choose the second operation, insert the string after the 6th character "wa", it will become "iwannawa".

How many operations does Binbin need to take at least to turn the string S into a string T ?

|S| represents the length of the string S.
|T| represents the length of the string T.

输入描述:

The first line contains a string S consisting of lowercase letters.

The second line contains a string T consisting of lowercase letters.

输出描述:

Output a number, indicating the minimum number of operations required to turn the string into the target string
示例1

输入

复制
binbindisliketowearskirts
binbinliketowearskirts

输出

复制
1
示例2

输入

复制
binbinliketowearskirts
binbinliketowearlolita

输出

复制
2