👤
a fost răspuns

#2118 minim lexicografic

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

Răspuns :

Răspuns:

#include<bits/stdc++.h>

using namespace std;

ifstream in("minlex.in");

ofstream out("minlex.out");

int main()

{

   char s[1000010],x[1000010];

   int n=0;

   in>>s;

   unsigned a=strlen(s);

   strcpy(x,s);

   strncat(s,s,a);

   for(int k=0;s[k+a+1];k++)

   {

       if(strncmp(x,s+k,a)>0)

       {

           strncpy(x,s+k,a);

           n=k;

       }

   }

   out<<n;

}

Explicație:

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari