(下面提到的 stri 表示以字符 si 开始的循环同构串,n 是 s 的长度
我对此算法过程中两个指针 i,j 的理解是:i,j 表示 s 的最小表示 一定存在于 stri,stri+1...strn, strj,strj+1..strn 中。这样理解可以解释当发现 si+k=sj+k 时(不妨设 si+k>sj+k)直接令 i=i+k+1, 因为不影响候选答案集合。
不知道我这么理解对不对?
然后我有一个地方不太明白:
为什么当 i>n 或 j>n 时 strmin(i,j) 就是答案?此时的候选答案集合是 strmin(i,j)...strn,但怎么证明 strmin(i,j) 一定就是答案呢?
请各位大佬指教。