Задача M. Циклические сдвиги

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Рассмотрим строку S, выступающую в качестве ключа в некотором симметричном алгоритме шифрования.

Для того, чтобы закодировать очередной символ входной последовательности, его необходимо переместить в начало такой строки путем ее циклического сдвига. Стоимость каждого отдельного сдвига определяется числом пропущенных позиций.

Требуется определить набор циклических сдвигов строки S с наименьшей общей стоимостью, необходимых для того, чтобы последовательно закодировать заданный набор символов T.

Формат входного файла

В начале входного файла "input.txt" записана строка S. Далее следует последовательность символов T, которую необходимо закодировать.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность сдвигов строки S, оптимальным образом кодирующих строку T.
При этом сдвиги вправо обозначаются положительными числами, влево — отрицательными.

Ограничения

Полагается, что обе строки состоят из цифр и строчных букв латинского алфавита.
При этом строка T не может содержать символы, отсутствующие в строке S.

0 < |S| ≤ 500, 0 < |T| ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
abc123ababab12abc12abxyz
ycxaa3z
2
-4
5
-3
0
-5
6
2
a5210zcba4210ycba3210xcb
aa42acx
0
-8
-1
7
2
2
1

0.111s 0.022s 15