Description
给定两个项链的表示，判断他们是否可能是一条项链。
Input
输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。
Output
如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’
第二行输出该项链的字典序最小的表示。 设L = 项链长度，L <= 1000000。
Sample Input
22343424232423223434
Sample Output
Yes2234342423
HINT
Source
///
/// _ooOoo_
/// o8888888o
/// 88" . "88
/// (| -_- |)
/// O\ = /O
/// ____/`---'\____
/// .' \\| |// `.
/// / \\||| : |||// \
/// / _||||| -:- |||||- \
/// | | \\\ - /// | |
/// | \_| ''\---/'' | |
/// \ .-\__ `-` ___/-. /
/// ___`. .' /--.--\ `. . __
/// ."" '< `.___\_<|>_/___.' >'"".
/// | | : `- \`.;`\ _ /`;.`/ - ` : | |
/// \ \ `-. \_ __\ /__ _/ .-` / /
/// ======`-.____`-.___\_____/___.-`____.-'======
/// `=---='
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
/// Buddha Bless, No Bug !
///
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define MAXN 100010
#define ll long long
string a, b;
int minma(
string x)
///最小循环同构
{
int len =
x.size();
int i =
0, j =
1, k =
0;
///初始化i = 0， j = 1
while(i < len && j < len && k < len)
///直接向后扫描
{
int t = x[(i + k) % len] - x[(j + k) % len];
///比较 x[i] 与 x[j] 两个循环同构串
if(t ==
0)
///如果扫描了 n 个字符仍相等，说明 x 只有1中字符构成，任意x[i]都是它的最小表示
k++
;
else///如果在 i+k 与 j+k 处发现不相等
{
if(t >
0)
///如果 x[i+k] > x[j+k]，那么x[i+1], x[i+2], ...,x[i+k]也都不是 x 的最小表示，这时就直接跳过这些位置
i += k +
1;
else///如果 x[i+k] < x[j+k]，那么x[j+1], x[j+2], ...,x[j+k]也都不是 x 的最小表示，这时就直接跳过这些位置
j += k + 1;
if(i == j)
///如果两指针相等，就让其中一个往后移，便于查找最小的循环同构
j++
;
k =
0;
}
}
return i < j ? i : j;
///返回最小循环同构的位置
}
int main()
{
cin>>a>>
b;
int lena = a.size(), lenb =
b.size();
if(lena !=
lenb)
printf("No\n");
else
{
int num_a =
minma(a);
int num_b =
minma(b);
for(
int k =
0; k < lena; k++
)
{
if(a[(num_a + k) % lena] != b[(num_b + k) %
lena])
{
printf("No\n");
return 0;
}
}
printf("Yes\n");
for(
int i =
0; i< lena; i++
)
cout<<a[(i + num_a) %
lena];
cout<<
'\n';
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11352127.html
相关资源：JAVA上百实例源码以及开源项目
