spoj
Състезание
Задача
E
Наименование
LOTARY

Условие

ЗАДАЧА. Е. ЛОТАРИЯ
---
Станчо много обича хазартните игри, но играе единствено такива, при които вероятността да спечели e почти 1. За съжаление, такива игри са рядкост. Наскоро, обаче, се появи нова и доста необичайна игра. При нея, всяка седмица се обявява предварително игрална конфигурация. Тя се състои от два елемента. Първият е низ, съставен от N малки латински букви (1 ≤ N ≤ 1 000 000), изписани върху дълга лента. Вторият е колело, върху периферията на което са изписани K малки латински букви (1 ≤ K ≤ 1 000 000). Колелото може да бъде завъртяно и спира така, че точно една от буквите се намира срещу поставен за целта показалец. Всеки играч може да си купи отрез от лентата, като сам определя началото и края на отреза, но има право на само един отрез. В края на седмицата, организаторите на играта извършват едно завъртане на колелото, при което се определя печеливша ротация за седмицата – този от всички K възможни низа, съставени от последователни букви от периферията на колелото, който започва от буквата застанала срещу показалеца, четен по посока на часовниковата стрелка. За да е сигурна печалбата на Станчо, той трябва да избере отрязък от лентата, който съдържа всички възможни ротации като поднизове. Той усети възможността за голяма печалба и иска от вас да напишете програма, която бързо да определя най-късия отрез (защото цената на отреза зависи от неговата дължина), който да си купи, така че да му гарантира печалбата.

На стандартния вход за дадени няколко игрални конфигурации. Всяка от тях се състои от ред с два низа от малки латински букви – низът от лентата и една от възможните ротации на колелото. Буквите от колелото са изписани по реда по който се срещат при обхождане на периферията по часовниковата стрелка. Т.е. при зададена на входа ротация abc, другите две възможни  ротации са bca и cab, а ротацията cba не е възможна.

За всяка зададена игрална конфигурация, програмата трябва да изведе на стандартния изход ред с единствено число – дължината на най-късия отрез, който Станчо може да купи, за да е сигурен, че ще спечели. Т.е. отрез, който да съдържа всички възможни ротации на колелото. Ако такъв отрез не съществува, програмата трябва да изведе на съответния ред 0.

Примерен вход:	
xabcdbax ab
alabala ab
abcabadba abc
abcdabadba abc	

Примерен изход:
6
3
5
0

Обяснение: 
За конфигурацията от първия ред на входния файл abcdba е най-късият отрез съдържащ двете възможни ротации ab и bа. За конфигурацията от втория ред, най-добрият отрез е aba, а за конфигурацията от  четвъртия ред няма подходящ отрез.

« Предходна страница Решение Въпрос