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