# PBinfo #2118 – minim lexicografic – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

Cerință
Să se determine poziția minimă k 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 minlex.in conține pe prima linie șirul de caractere.

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

Restricții și precizări

2 ≤ N ≤ 100.000

Exemplu:
minlex.in

ALFABET
minlex.out

3
Explicație
Rotațiile posibile:
k=0 → ALFABET
k=1 → LFABETA
k=2 → FABETAL
k=3 → ABETALF
k=4 → BETALFA
k=5 → ETALFAB
k=6 → TALFABE
Șirul minim lexicografic obținut: ABETALF, pentru o rotație cu 3 poziții spre stânga a șirului inițial.

## Cod sursă C++

```cpp
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("minlex.in");
ofstream g("minlex.out");
char S[100001];
int N;
bool compara(char *S, int i, int j)
{
    int k;
    for (k=0;k<N;k++)
    {
        if (S[i]<S[j]) return false;
        if (S[i]>S[j]) return true;
        i=(i+1)%N;
        j=(j+1)%N;
    }
    return true;
}
int minlex(char *S)
{
    int poz=0, i;
    for (i=1;i<N;i++)
        if (compara(S,poz,i)) poz=i;
    return poz;
}
int main()
{
    f>>S;
    f.close();
    N=strlen(S);
    g<<minlex(S)<<'\n';
    g.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2118)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2118/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2118/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)