CF156A 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.

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.

由 ChatGPT 5 翻译