例题 $158$

最小表示法的思想是很暴力的，每次两个指针$i$, $j$不停移动，对$i$, $j$后面的子串进行比较。

设两个后缀的$lcp$为$k$。

要不然$k = n$，有循环节，且$i$，$j$不相等，则必经历过一整个循环节，可以退出，$i$，$j$均为答案。

否则$k < n$，不妨设$i$后缀字典序更大，则$i ~~ i + k$后缀均报废。

因为平移后任意 $ii$ 总有对应 $jj$比它更优。

所以$i += k + 1$，跳过一段。

不要看这个优化非常显然就没什么用，实际上他是改变复杂度的关键一步。

没有这一步的话枚举$i，j$，进行比较总复杂度最坏可以$O(n ^ 3)$级别。

而加上优化后，简单分析可得， 单次操作后，$i + j$的和增加了至少$k$。

$i + j$最大为 $O(n)$ 级别，而$k$的总和也为$O(n)$级别，所以总复杂度降为$O(n)$，实现了一个质的飞跃。

代码如下。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 20;

int n, m;
char a[N << 1], b[N << 1];

int solve(char *s)
{
    int i = 1, j = 2;
    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) j ++;
    }
    return min(i, j);
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    for(int i = 1; i < n; i ++) a[i + n] = a[i], b[i + n] = b[i];
    int x = solve(a);
    int y = solve(b);
    a[x + n] = b[y + n] = 0;
    if(strcmp(a + x, b + y)) puts("No");
    else
    {
        puts("Yes");
        printf("%s", a + x);
    }
    return 0;
}