https://oi-wiki.org/string/minimal-string/
强烈建议直接阅读原文 下文为本人碎碎念 主要帮助记忆与理解
暴力做法
定义三个指针i,j,k分别表示指向的待比较字符串的起始位置1, 起始位置2 已经比较的长度
1.开始比较 如果cs[i] == cs[j] k++
如果不等的话 谁大谁往后移动 并且重新设置 k = 0; 由于可能出现i == j的情况 所以当出现这种情况时 j++
最后比较完毕以后剩下的最小的就是答案的起始位置 min(i,j) => 其实这里由于每次都+1 所以可以保证 i <=j 直接返回i就行
上述算法容易被构造卡成n^2 例如 aaa....ab
最小表示法
考虑优化上述做法
相等的部分必然不可能做为起点 所以可以一次跳k步
由于一次跳了k步 所以存在 i > j的情况 这时候必须取min(i,j)