A8419. Message
编程题
普及/提高-
知识点
题目描述
Dr. Moriarty is about to send a message to Sherlock Holmes. He has a string $s$ .
String $p$ is called a substring of string $s$ if you can read it starting from some position in the string $s$ . For example, string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".
Dr. Moriarty plans to take string $s$ and cut out some substring from it, let's call it $t$ . Then he needs to change the substring $t$ zero or more times. As a result, he should obtain a fixed string $u$ (which is the string that should be sent to Sherlock Holmes). One change is defined as making one of the following actions:
- Insert one letter to any end of the string.
- Delete one letter from any end of the string.
- Change one letter into any other one.
Moriarty is very smart and after he chooses some substring $t$ , he always makes the minimal number of changes to obtain $u$ .
Help Moriarty choose the best substring $t$ from all substrings of the string $s$ . The substring $t$ should minimize the number of changes Moriarty should make to obtain the string $u$ from it.
String $p$ is called a substring of string $s$ if you can read it starting from some position in the string $s$ . For example, string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".
Dr. Moriarty plans to take string $s$ and cut out some substring from it, let's call it $t$ . Then he needs to change the substring $t$ zero or more times. As a result, he should obtain a fixed string $u$ (which is the string that should be sent to Sherlock Holmes). One change is defined as making one of the following actions:
- Insert one letter to any end of the string.
- Delete one letter from any end of the string.
- Change one letter into any other one.
Moriarty is very smart and after he chooses some substring $t$ , he always makes the minimal number of changes to obtain $u$ .
Help Moriarty choose the best substring $t$ from all substrings of the string $s$ . The substring $t$ should minimize the number of changes Moriarty should make to obtain the string $u$ from it.
输入格式
The first line contains a non-empty string $s$ , consisting of lowercase Latin letters. The second line contains a non-empty string $u$ , consisting of lowercase Latin letters. The lengths of both strings are in the range from $1$ to $2000$ , inclusive.
输出格式
Print the only integer — the minimum number of changes that Dr. Moriarty has to make with the string that you choose.
输入输出样例
输入 #1
aaaaa aaa
输出 #1
0
输入 #2
abcabc bcd
输出 #2
1
输入 #3
abcdef klmnopq
输出 #3
7
说明/提示
In the first sample Moriarty can take any substring of length $3$ , and it will be equal to the required message $u$ , so Moriarty won't have to make any changes.
In the second sample you should take a substring consisting of characters from second to fourth ("bca") or from fifth to sixth ("bc"). Then you will only have to make one change: to change or to add the last character.
In the third sample the initial string $s$ doesn't contain any character that the message should contain, so, whatever string you choose, you will have to make at least $7$ changes to obtain the required message.
In the second sample you should take a substring consisting of characters from second to fourth ("bca") or from fifth to sixth ("bc"). Then you will only have to make one change: to change or to add the last character.
In the third sample the initial string $s$ doesn't contain any character that the message should contain, so, whatever string you choose, you will have to make at least $7$ changes to obtain the required message.