I. Строчечки

Кирилл написал строку, а Дима утверждает, что получил свою строку циклическим сдвигом строки Кирилла вправо на несколько шагов. Сдвиг строки abcde на 2 позиции вправо даёт deabc.

Проверьте, правда ли это, и если да — найдите наименьший возможный размер сдвига.

Основа решения — старое наблюдение: все циклические сдвиги строки $A$ — это подстроки длины $n$ строки $A + A$.

Сдвиг вправо на $r$ даёт строку $A[n-r..] + A[..n-r)$, то есть подстроку $A + A$, начинающуюся в позиции $n - r$. Значит, надо найти все вхождения $B$ в $A + A$ на позициях $0 \le p < n$ и взять $r = (n - p) \bmod n$.

Наименьший $r$ — это $r = 0$, если $A = B$, и иначе наибольшее подходящее $p$.

Искать вхождения — снова КМП по склейке $B + \# + A + A$. Длина склейки около $3n$, то есть до $3 \cdot 10^6$ — по времени и памяти проходит.

Отдельно стоит подумать, почему нельзя просто перебрать все $n$ сдвигов и сравнить: это $O(n^2)$ и при $n = 10^6$ безнадёжно.

Строки состоят из больших и маленьких букв, так что регистр важен: A и a — разные символы.

Первые две строки содержат строки Кирилла и Димы.

Длины строк одинаковы, не превосходят $10^6$ и не равны нулю. Строки состоят из больших и маленьких латинских букв.

Единственное число — наименьший размер сдвига, или $-1$, если такого сдвига не существует.