部分题解有误
查看原帖
部分题解有误
175590
Zxx200611楼主2022/4/13 17:58

在最小表示法的常规算法(维护两个指针以及匹配长度)中,当匹配长度等于字符串长度 nn 时直接返回。

许多题解对此的解释是,当匹配长度达到 nn 时,整个字符串由同种字符构成。
这种说法是错误的,例如,字符串为 3 1 2 3 1 2 3 1 2。算法执行过程中的一步为,第一个指针指向第二个 11,第二个指针指向第一个 11,此时匹配长度达到 nn,退出循环。然而整个字符串并不由同种字符构成。

正确的解释应该是,当匹配长度达到 nn 时,子串 [i,j1][i,j-1](假设 i<ji<j)是原串的循环节,且由于 jj 的后移,循环节中其他位置 [i+1,j1][i+1,j-1] 不可能是原串的最小表示,因此 iijj 为原串最小表示。

请撤下或要求修改如下题解:
https://www.luogu.com.cn/blog/new2zy/solution-p1368
https://www.luogu.com.cn/blog/loveofjewelry/solution-p1368
https://www.luogu.com.cn/blog/Huah/solution-p1368

同时,由于一些原因,某些题解不属于本题,请求一并处理:
https://www.luogu.com.cn/blog/user26661/solution-p1368
https://www.luogu.com.cn/blog/txcakakak/solution-p1368
https://www.luogu.com.cn/blog/hsfzLZH1/xian-xing-shi-jian-zha-zhao-zhong-wei-shuo
https://www.luogu.com.cn/blog/user35973/solution-p1368

2022/4/13 17:58
加载中...