И снова Тындекс догоняет и перегоняет своих конкурентов! В ответ на выход Жужль Хром явился новый браузер — Тындекс.Бром!
С каждым днём растёт популярность нового браузера. И дело даже не в том, что в него встроен Тындекс.Бар, который, после покупки Тындекс.Бутылки и подключения её к USB-порту, автоматически наполняет тару прекрасным коньяком 1664 года; а благодаря продуманному взаимодействию с пользователем.
Возьмём, например, систему автоматического исправления адреса. Вы ввели codehorses вместо codeforces? Унылый Жужль Хром уныло скажет, мол, нет такого адреса. В то же время Тындекс.Бром автоматически подберёт ближайший адрес и отправит вас именно туда. Гениально!
Как же работает эта замечательная система? Очень просто! Для каждого потенциального адреса вычисляется функция ошибки F по следующим правилам:
- для каждой буквы ci из потенциального адреса c находится ближайшая позиция j этой же буквы во введенном пользователем адресе s. К F прибавляется модуль разности этих позиций |i - j|. То есть для каждого i (1 ≤ i ≤ |c|) позиция j выбирается таким образом, что ci = sj, а |i - j| минимально.
- если такой буквы ci во введенном пользователем адресе нет, то к F прибавляется длина потенциального адреса |c|
После вычисления значений функции ошибки для всех потенциальных адресов выбирается наиболее подходящий.
Для того чтобы лучше разобраться в особенностях описанного выше способа, рекомендуется реализовать алгоритм вычисления функции F для заданного пользователем адреса и некоторого набора потенциальных адресов. Дерзайте!
Выходные данные
В каждой из n строк выходного файла выведите одно число: значение функции ошибки при выборе текущего потенциального адреса.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).