View source for 2118 - Minim Lexicografic

Se consideră un șir de caractere format din <code>N</code> caractere literă mare ale alfabetului englez. Șirul poate fi rotit circular spre stânga cu <code>k</code> poziții.

= Cerință =
Să se determine poziția minimă <code>k</code> cu care poate fi rotit circular spre stânga șirul inițial astfel încât șirul obținut să fie minim lexicografic.

= Date de intrare =
Fișierul de intrare <code>minlex.in</code> conține pe prima linie șirul de caractere.

= Date de ieșire =
Fișierul de ieșire <code>minlex.out</code> va conține pe prima linie numărul natural <code>k</code>.

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>

= Exemplu: =
<code>minlex.in</code>
 ALFABET
<code>minlex.out</code>
 3

=== Explicație ===
Rotațiile posibile:

<code>k=0</code> → <code>ALFABET</code>

<code>k=1</code> → <code>LFABETA</code>

<code>k=2</code> → <code>FABETAL</code>

<code>k=3</code> → <code>ABETALF</code>

<code>k=4</code> → <code>BETALFA</code>

<code>k=5</code> → <code>ETALFAB</code>

<code>k=6</code> → <code>TALFABE</code>

Șirul minim lexicografic obținut: <code>ABETALF</code>, pentru o rotație cu <code>3</code> poziții spre stânga a șirului inițial.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

sys.stdin = open('minlex.in', 'r')
sys.stdout = open('minlex.out', 'w')

s = input()
sir = [''] * (2 * len(s))
i = 0
h = len(s)
while s[i] != '\0':
    sir[i] = s[i]
    sir[h + i] = s[i]
    i += 1

iva = 0
for i in range(h):
    if ''.join(sir[i:]) < s:
        s = ''.join(sir[i:])
        iva = i

print(iva)

</syntaxhighlight>