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

Технічні умови. Програма Shift читає з пристрою стандартного введення рядок символів S, а в другому – підрядок А. Довжина кожного рядка не перевищує 106. Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади

Введення

ABCDA
AA

Виведення

1

Введення

ABACAB
ABA

Виведення

2

 

© LIKT 1998-2018