本文主要是介绍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("No\n");else printf("Yes\n");}
}
这篇关于Fzu 2154 YesOrNo【最小表示法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
