前言

$\color{white}{问号}$这个我是讲解LYD大佬所在书上讲解的内容，有书者可读第$75$到$77$页（河南电子音像出版社）大佬讲的详细作者我讲的不详细，没书者可继续阅读。

相关题目：158. 项链

基础概念

$\color{white}{问号}$给你一个字符串(设它为$“S[N]”$)，如果我们不断把最后一个字符放在开头，最终会得到$N$个字符串，我们称这几个字符串是循环同构的。在这些字符串里，字典序最小的一个，即是$S$的最小表示。

$\color{white}{问号}$例如某一个字符串是$“fxtnb”$,则它的$5$个循环同构的字符串等于$“fxtnb”、“bfxtn”、“nbfxt”、“tnbfx”、“xtnbf”$，显然，它的最小表示是$“bfxtn”$。我们定义$B[i]$来表示从$i$开始的循环同构字符串，即$S[i\sim n]+S[1\sim i-1]$

$\color{white}{问号}$如何快速求出一个字符串的最小表示？事实上，可以使用$O(n)$的效率求出。我们首先复制一个字符串$S$放到字符串$S$的后面，形成字符串$SS$。显然，$B[i]=SS[i\sim i+n+1]$。

$\color{white}{问号}$我们观察以下的比较过程：

$S=”bacacabc”,i=2,j=4,k=3$

$\color{white}{问号}$如果在$i+k$和$j+k$处不相等，假设$SS[i+k]>SS[j+k]$，可得知$B[i]$不是$S$的最小表示(存在一个更小的循环同构串$B[j]$)。除此之外，我们还可得知$B[i+1],B[i+2],…,B[i+k]$也都不是$S$的最小表示。因为这是对于$1\leq p\leq k$，存在一个比$B[i+k]$更小的循环同构串$B[j+p]$(从$i+p$与$j+p$开始向后扫描，同样会发现$p=k$时不相等，并且$SS[i+k]>SS[j+k]$)。

$\color{white}{问号}$这个算法通过两个指针$(i,j)$不断向后移动的形式，尝试比较每两个循环同构串的大小。利用上面的性质，可及时排除掉不同的选项。当其中一个指针移到结尾时，既考虑过所有情况(二元组$(B[i],B[j])$)，即可得到了最小表示。

$\color{white}{问号}$最后附上LYD大佬的代码：

int n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[n+i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n) {
    for (k = 0; k < n && s[i+k] == s[j+k]; k++);
    if (k == n) break;
    if (s[i+k] > s[j+k]) {
        i = i + k + 1;
        if (i == j) i++;
    } else {
        j = j + k + 1;
        if (i == j) j++;
    }
}
ans = min(i, j);