Fzu 2154 YesOrNo【最小表示法】

Fzu 2154 YesOrNo【最小表示法】

 Problem 2154 YesOrNo

Accept: 160    Submit: 351
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

A国认为如果字符串a可以通过操作X变成字符串b，就认为是一样的字符串。

操作X：将字符串分为两部分，然后调换位置，操作次数不限。W=xy,W’=yx。

 Input

有多组测试数据，处理到文件结尾。每组测试数据包含两个个字符串（包含英文字符和数字，长度为[1,500000]）。

 Output

对于每组测试数据，如果两个字符串是相同的，输出Yes或者是No。

 Sample Input

YesOrNo NoOrYes YesOrNo rNoYesO

 Sample Output

No  Yes
思路：

截取操作其实相当于可以让字符串进行循环（也就是将字符串看成一个环，我们可以视为任意一个位子作为起点的字符串）

那么我们如果两个字符串以此进行的最小字典序表示法相等，那么两个字符串肯定就可以通过一个变成另外一个。

那么直接O（n）跑最小表示法即可。

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
char a[3004000];
char b[3004000];
char c[3004000];
char d[3004000];
int l,n;
int MinimumRepresentation(char b[])
{l=n;int i = 0, j = 1, k = 0, t;while(i < l && j < l && k < l) {t = b[(i + k) >= l ? i + k - l : i + k] - b[(j + k) >= l ? j + k - l : j + k];if(!t) k++;else{if(t > 0) i = i + k + 1;else j = j + k + 1;if(i == j) ++ j;k = 0;}}return (i < j ? i : j);
}
void Getb()
{int tmp=MinimumRepresentation(a);for(int z=0;z<n;z++){b[z]=a[(z+tmp)%n];}
}
void Getd()
{int tmp=MinimumRepresentation(c);for(int z=0;z<n;z++){d[z]=c[(z+tmp)%n];}
}
int main()
{while(~scanf("%s",a)){n=strlen(a);Getb();scanf("%s",c);Getd();int flag=0;for(int i=0;i<n;i++){if(b[i]!=d[i])flag=1;}if(flag==1)printf("Non");else printf("Yesn");}
}