The cyclic suffixes (Easy)
The cyclic suffixes (Easy)
Consider the string S = s_1s_2s_3...s_{n - 1}s_n on alphabet Σ. The cyclic extension of order m of a string S is a strings_1s_2s_3...s_{n - 1}s_ns_1s_2... that consists of m characters. It means that we append the string S to itself until we get the desired length and take the prefix of length m.
The cyclic stringŠ is an infinite cyclic extension of S.
Consider the suffixes of cyclic string Š. Obviously, there exists no more than |S| different suffixes: the (n+1)-th suffix matches with the first one, the (n+2)-th matches with the second and so on. Moreover, the number of different suffixes can be less than |S|. For example, if S = abab, the first four suffixes of a cyclic string Š are:
Š_1 = ababababab...Š_2 = bababababa...Š_3 = ababababab...Š_4 = bababababa...
There is only two different suffixes, while |S| = 4.
Sort the first |S| suffixes of Š lexicographically. If two suffixes match, put first the suffix with lowest index. Now answer the question: what place does the string Š take in this list?
For example, consider the string S = cabcab:
(1) Š_2 = abcabcabca...(2) Š_5 = abcabcabca...(3) Š_3 = bcabcabcab...(4) Š_6 = bcabcabcab...(5) Š_1 = cabcabcabc...(6) Š_4 = cabcabcabc...
The cyclic string Š = Š_1 takes the fifth place.
You are given a string S. Find the position of cyclic string Š in the list of suffixes.
Input data
One string S (1 ≤ |S| ≤ 30), consisting of lowercase Latin letters.
Output data
Print the position of the string Š in the list of the first |S| suffixes.
Examples
abracadabra
3