a b a b c
b a b c a
a b c a b
b c a b a
c a b a b
字典序最小的串-原串的最小表示法
暴力-O(n^2)
堆-O(nlogn)
破环成链
a b a b c a b a b c
| |
| |
| |
双指针O(n)
对比
s1 = s.substr(i,n)
s2 = s.substr(j,n)
i i+k i+n
j j+k j+n
i+k和j+k是第一个不同的字符
1 s[i+k]>s[j+k]:
i开头的不是最小表示
并且 [i,i+k]中开头的长度为n的串也不是
证:此时可以找到i' in [i,i+k] ,j' in [j,j+k]
i i' i+k i+n
j j' j+k j+n
因为以i'开头的[i',i'+n]一定<[j',j'+n]
所以i = i+k+1
2 s[i+k]<s[j+k]:
同理可推
j = j+k+1
3 s1 == s2:break
此时出现循环串 且覆盖了[i,i+n] [j,j+n],那么原串 = 循环串
且j-i刚好是一个循环节,则说明j从i走到j都没找到一个比i更小的
即把一个循环节枚举完了,相当于把所有可能串都枚举完了
i
ab ab ab ab
\| \| \|
ab ab ab
j
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2000010;
int n;
char a[N], b[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;//如果k都已经走了n了 s[i+n] == s[j+n] 则说明是循环串了
if (s[i + k] > s[j + k]) i += k + 1;
else j += k + 1;
if (i == j) j ++ ;//没必要比较相同起点,所以让j走到下一个位置
}
int ans = min(i, j);//结束时靠前的就是答案,因为字典序大的我们都让它+k+1了
// 给最小表示法的终止位置标0表示字符串结尾 方便strcmp()比较
s[ans + n] = 0;
return ans;
}
int main()
{
scanf("%s%s", a, b);
n = strlen(a);
memcpy(a + n, a, n);
memcpy(b + n, b, n);
int x = get_min(a), y = get_min(b);
if (strcmp(a + x, b + y)) puts("No");
else
{
puts("Yes");
puts(a + x);
}
return 0;
}