Циклічні суфікси

Розглянемо рядок \textbf{S = s_1s_2s_3 \ldots s_{n-1}s_n} над алфавітом $\text{Sigma}$. Циклічним розширенням порядку $m$ рядка $\text{S}$ називається рядок s_1s_2s_3 \ldots s_{n-1}s_ns_1s_2 \ldots довжини $m$. Це означає, що ми дописуємо рядок $\text{S}$ сам до себе, доки не отримаємо потрібну довжину, і беремо префікс довжини $m$.

Циклічним рядком \textbf{Š} називається нескінченне циклічне розширення рядка $\text{S}$.

Розглянемо суфікси циклічного рядка \textbf{Š}. Очевидно, існує не більше $|\text{S}|$ різних суфіксів: (n+1)-ий суфікс збігається з першим, (n+2)-ий збігається з другим, і так далі. Фактично, різних суфіксів може бути навіть менше. Наприклад, якщо \textbf{S} = abab, перші чотири суфікси циклічного рядка \textbf{Š} такі:

\textbf{Š}_1 = ababababab \ldots

\textbf{Š}_2 = bababababa \ldots

\textbf{Š}_3 = ababababab \ldots

\textbf{Š}_4 = bababababa \ldots

Тут лише два різних суфікси, хоча |\textbf{S}| = 4.

Відсортуємо перші $|\text{S}|$ суфіксів \textbf{Š} лексикографічно. Якщо два суфікси збігаються, спочатку розміщується суфікс з меншим індексом. Питання: на якому місці знаходиться сам рядок \textbf{Š} у цьому списку?

Наприклад, для рядка \textbf{S} = cabcab:

(1) \textbf{Š}_2 = abcabcabca \ldots

(2) \textbf{Š}_5 = abcabcabca \ldots

(3) \textbf{Š}_3 = bcabcabcab \ldots

(4) \textbf{Š}_6 = bcabcabcab \ldots

(5) \textbf{Š}_1 = cabcabcabc \ldots

(6) \textbf{Š}_4 = cabcabcabc \ldots

Тут циклічний рядок \textbf{Š} = \textbf{Š}_1 займає п'яте місце.

Вам задано рядок $\text{S}$. Знайдіть позицію циклічного рядка \textbf{Š} у цьому списку.