Question

Se spune ca sirul y1, y2, ..., yn este o permutare circulara cu p pozitii a sirului x1, x2, ..., xn daca y1=xp+1, y2=xp+2, ..., yn=xp+n, unde indicii mai mari ca n se considera modulo n, adica indicele k, cu k>n se refera la elementul de indice k-n.

Cerinta

Pentru doua siruri date determinati daca al doilea este o permutare circulara a primului sir.

Date de intrare

Pe prima linie a fisierului de intrare circular.in este scris numarul natural n. Pe liniile urmatoare sunt doua siruri de caractere de lungime n, formate numai din litere mari ale alfabetului latin.

Date de iesire

Prima linie a fisierului circular.out se va scrie cel mai mic numar natural p pentru care sirul de pe linia a treia este o permutare circulara cu p pozitii a sirului de pe linia a doua, sau numarul -1 daca nu avem o permutare circulara.

Restrictii

1 <= n <= 20000
Exemplu

circular.in circular.out
10
ABCBAABBAB
BABABCBAAB 7



AM NEVOIE DE AJUTOR!!! O AM CA TEMA SI NU MA DESCURC! VA ROGGG!!!

Answer 1

Răspuns:

#include <iostream>

#include <cstring>

#include <fstream>

using namespace std;

ifstream f("circular.in");

ofstream g("circular.out");

char s1[100], s2[100], tmp[100], ch[1];

int n,i, p, gasit,lens1;

int main()

{

   f >> n; f.get();

   f.getline(s1,100);

   f.getline(s2,100);

   lens1=strlen(s1);

   for (p=1; p<lens1; p++)

   {

       tmp[0]=0; ch[0]=0;

       ch[0]=s1[0];

       strcpy(tmp,s1+1);

       strcpy(s1,tmp);

       strcat(s1,ch);

       if (strcmp(s1,s2)==0)

       {

           gasit=1;

           break;

       }

   }

   if (gasit)

       g << p;

   else g << -1;

   return 0;

}

Explicație:

facem repetat deplasarile spre stanga, primul se duce pe ultima pozitie.

Ar fi util sa faci pe hartie...

Fie datele sunt n=4 si s1="ABCD", ATUNCI DEPLASARILE SUNT

BCDA

CDAB

DABC