题目描述
有一天,达达捡了一条价值连城的宝石项链,但是,一个严重的问题是,他并不知道项链的主人是谁!
在得知此事后,很多人向达达发来了很多邮件,都说项链是自己的,要求他归还(显然其中最多只有一个人说了真话)。
达达要求每个人都写了一段关于自己项链的描述: 项链上的宝石用数字0至9来标示。
一个对于项链的表示就是从项链的某个宝石开始,顺指针绕一圈,沿途记下经过的宝石,比如项链: 0-1-2-3 ,它的可能的四种表示是0123、1230、2301、3012。
达达现在心急如焚,于是他找到了你,希望你能够编写一个程序,判断两个给定的描述是否代表同一个项链(注意,项链是不会翻转的)。
也就是说给定两个项链的表示,判断他们是否可能是一条项链。
样例
输入样例:
2234342423
2423223434
输出样例:
Yes
2234342423
算法1
(字符串的最小表示) $O(n)$
具体想法见lyd《算法进阶指南(第5版)》P76
时间复杂度
因为每次隔位对字符串进行比较,如果相同就不断+1,两个字符串最多$2n$次比较,所以时间复杂度为$O(n)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2000010;
char a[N], b[N];
int n;
int get_min(char s[]){
int i = 0, j = 1;
while (i <= n && j <= n){
int k = 0;
while (k < n && s[i + k] == s[j + k]) k ++;
if (k == n) break;
if (s[i + k] > s[j + k]) i += k + 1;
else j += k + 1;
if (i == j) i ++;
}
int res = min(i, j);
s[res + n] = '\0';
return res;
}
int main(){
scanf("%s%s", a, b);
n = strlen(a);
memcpy(a + n, a, n);
memcpy(b + n, b, n);
int ap = get_min(a), bp = get_min(b);
if (strcmp(a + ap, b + bp)) puts("No");
else {
puts("Yes");
puts(a + ap);
}
return 0;
}