在最小表示法的常规算法(维护两个指针以及匹配长度)中,当匹配长度等于字符串长度 n 时直接返回。
许多题解对此的解释是,当匹配长度达到 n 时,整个字符串由同种字符构成。
这种说法是错误的,例如,字符串为 3 1 2 3 1 2 3 1 2。算法执行过程中的一步为,第一个指针指向第二个 1,第二个指针指向第一个 1,此时匹配长度达到 n,退出循环。然而整个字符串并不由同种字符构成。
正确的解释应该是,当匹配长度达到 n 时,子串 [i,j−1](假设 i<j)是原串的循环节,且由于 j 的后移,循环节中其他位置 [i+1,j−1] 不可能是原串的最小表示,因此 i 或 j 为原串最小表示。
请撤下或要求修改如下题解:
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