BZOJ 1398: Vijos1382寻找主人 Necklace（最小表示法）

Description

给定两个项链的表示，判断他们是否可能是一条项链。

Input

输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

Output

如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’ 第二行输出该项链的字典序最小的表示。 设L = 项链长度，L <= 1000000。

Sample Input

2234342423

2423223434

Sample Output

Yes

2234342423

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 longstring a, b;int minma(string x)///最小循环同构 {int len = x.size();int i = 0, j = 1, k = 0;///初始化i = 0， j = 1while(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

总结

以上是生活随笔为你收集整理的BZOJ 1398: Vijos1382寻找主人 Necklace（最小表示法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。