Codeforces Round 110 (Div. 1) |
---|
Закончено |
Доктор Мориарти посылает сообщение Шерлоку Холмсу. В его распоряжении имеется строка s.
Строка p называется подстрокой строки s, если ее можно прочитать, начиная с некоторой позиции в строке s. Например, у строки «aba» есть шесть подстрок: «a», «b», «a», «ab», «ba», «aba».
Доктор Мориарти планирует вырезать из строки s некоторую подстроку, назовем ее t. Потом он должен ноль или более раз изменить вырезанную подстроку t. В результате должна получиться фиксированная строка u (именно ее нужно отправить Шерлоку Холмсу). За одно изменение считается одно из следующих действий:
Мориарти очень умен, поэтому после выбора какой-то подстроки t он всегда делает минимальное количество изменений, чтобы получить u.
Помогите Мориарти выбрать среди всех подстрок строки s наилучшую подстроку t такую, что количество сделанных им изменений для получения из нее строки u будет минимально.
В первой строке дана непустая строка s, состоящая из строчных букв латинского алфавита. Во второй строке дана непустая строка u, состоящая из строчных букв латинского алфавита. Длины обоих строк находятся в пределах от 1 до 2000 включительно.
Выведите единственное число — минимальное количество изменений, которые придется выполнить доктору Мориарти с подстрокой, которую Вы выберете.
aaaaa
aaa
0
abcabc
bcd
1
abcdef
klmnopq
7
В первом примере Мориарти может взять любую подстроку длины 3, и она будет равна требуемому сообщению u, так что никаких изменений Мориарти делать не придется.
Во втором примере надо взять подстроку, состоящую из символов со второго по четвертый («bca») или с пятого по шестой («bc»). Тогда придется сделать всего одно изменение: заменить или добавить последний символ.
В третьем примере исходная строка s не содержит ни одного символа, который должен быть в сообщении, так что, какую подстроку не возьми, придется сделать как минимум 7 изменений, чтобы получить требуемое сообщение.
Название |
---|