why W/A DCP-63: Cyclic String plz help

Dev Skill archived problems can be discussed here.

why W/A DCP-63: Cyclic String plz help

by joy25896 » Tue Apr 04, 2017 12:46 am

Code: Select all
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define MAX 1000000
int minLexCyc(const char *x) {
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x);
    while(j+k <= (l<<1)) {
        if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) {
            i=j++;
            k=p=1;
        } else if (a<b) {
            j+=k;
            k=1;
            p=j-i;
        } else if (a==b && k!=p) {
            k++;
        } else {
            j+=p;
            k=1;
        }
    }
    return i;
}
int main()
{
     int T;
     cin>>T;
     cin.ignore();
     while(T--)
     {



    char str1[MAX],str2[MAX];
    cin>>str1>>str2;
    int a=minLexCyc(str1),b=minLexCyc(str2),i,n=strlen(str1);
for(i=0;i<n;i++){
        if(str1[(a+i)%n]!=str2[(b+i)%n]){
                cout<< "NO"<<endl;
                return 0;
        }
}
cout<< "YES"<<endl;
     }
    return 0;
}
 
Posts: 30
Joined: Wed Nov 16, 2016 3:29 pm
Location: dhaka bangladesh

Who is online
Users browsing this forum: No registered users and 2 guests
cron