前言
$\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);
Good,好文章。
谢谢
白色的问号?
stO 这都能发现
dark reader:你把我忽略了?
这插件很不错欸,白色的字全都出来
神级插件护眼
解密专用插件支持!!!