The cyclic suffixes (Easy)#5287

The cyclic suffixes (Easy)

1 sekunt
64 megabaýt
Örän ýeňil

Consider a string \mathbf{S} = s_1s_2s_3\dots s_n over an alphabet , where |\mathbf{S}| = n.

A cyclic extension of order of the string is a string of characters, given by s_1s_2s_3\dots s_ns_1s_2\dots, that is, we concatenate copies of to itself until reaching length , and then take the prefix of length .

The cyclic string \mathbf{\breve{S}} is the infinite cyclic extension of .

Consider the suffixes of the cyclic string \mathbf{\breve{S}}. Obviously, there are at most different suffixes: the (n+1)-th suffix coincides with the first one, the (n+2)-th coincides with the second one, and so on. Moreover, the number of distinct suffixes can be less than . For example, if \mathbf{S} = abab, the first four suffixes of the cyclic string \mathbf{\breve{S}} are:

\begin{align*} \mathbf{\breve{S}}_1 &= \mathbf{ababababab}\ldots \\ \mathbf{\breve{S}}_2 &= \mathbf{bababababa}\ldots \\ \mathbf{\breve{S}}_3 &= \mathbf{ababababab}\ldots \\ \mathbf{\breve{S}}_4 &= \mathbf{bababababa}\ldots \end{align*}

Here, there are only two distinct suffixes, while n = 4.

Sort the first suffixes of \mathbf{\breve{S}} lexicographically. If two suffixes are identical, the one with the lower index comes first. Now, answer the following question: in what position does the string \mathbf{\breve{S}} itself (i.e., \mathbf{\breve{S}}_1) appear in this ordering?

For example, consider the string \mathbf{S} = cabcab:

\begin{align*} (1)\ &\mathbf{\breve{S}}_2 = \mathbf{abcabcabca}\ldots \\ (2)\ &\mathbf{\breve{S}}_5 = \mathbf{abcabcabca}\ldots \\ (3)\ &\mathbf{\breve{S}}_3 = \mathbf{bcabcabcab}\ldots \\ (4)\ &\mathbf{\breve{S}}_6 = \mathbf{bcabcabcab}\ldots \\ (5)\ &\mathbf{\breve{S}}_1 = \mathbf{cabcabcabc}\ldots \\ (6)\ &\mathbf{\breve{S}}_4 = \mathbf{cabcabcabc}\ldots \end{align*}

Here, the cyclic string \mathbf{\breve{S}} = \mathbf{\breve{S}}_1 takes the fifth place in the list.

You are given a string . Find the position of the cyclic string \mathbf{\breve{S}} among the sorted first suffixes.

Giriş

The input contains a single string (1 \leq |\mathbf{S}| \leq 30), consisting of lowercase Latin letters.

Çykyş

Print the position of \mathbf{\breve{S}} in the lexicographically sorted list of the first suffixes.

Mysallar

1-nji mysal

Loading
Loading