Задача Shift. Дана строка S и строка А. Необходимо найти циклический сдвиг строки S с максимальным количеством вхождений в него строки А и вывести не сам циклический сдвиг, а именно максимальное количество вхождений среди всех сдвигов. Например, если в строке ABCDA искать вхождения строки АА, то максимальное количество вхождений равно 1 (в сдвигах AABCD или BCDAA). В строчках гарантровано отсутствуют пробелы.
Технические условия. Программа Shift читает с устройства стандартного ввода строку символов S, а в следующей строке – подстроку А. Длина каждой строки не превышает 106. Программа выводит на устройство стандартного вывода единственное число - искомую величину.
Примеры
|
Ввод ABCDA |
Вывод 1 |
|
Ввод ABACAB |
Вывод 2 |