二分法求解原理（转）
设当前串为s[l..r] 则s[l..r]的最小位置来自于s[l,mid]（记为A） s[mid+1,r]（记为B）的最小位置
现在只要将A B 中较优的可以作为s[l...r]的最优值。
比较A B的方法 比较s[A..B-1]与S[B..T]这二个长度相等的串
1.若串S[A..B-1]小于串S[B..T]，那么A必优于B。
2.若串S[A..B-1]大于串S[B..T]，那么B必优于A。
3.若串S[A..B-1]等于串[B..T]，分情况讨论：（设从A开始的长度为N的串为S1，B开始的长度为N的串为S2）
1）若S1<S2 那么 A较优
2）若S1=S2那么 A也较优（A的位置靠前）
3）若S1>S2那么 T+1..len中有一个位置K 比 A与B 优，此时选A选B无影响//实际上如果满足这个条件,则最优值必然在这两个区间外，因为从s[t+1]开始的字符串跟s[b]开始的字符串一样！
综上所述，当S[A..B-1]=S[B..T]时，选A
usaco官方题解（转）
v[i]表示，从i开始的v[i]长度是所有v[i]长度中最小的。我们把读入的s变为s+s，方便记录。例如对于‘avdwfasa’，v[1]等于1，而不能等于2，因为as<aw。
我们不断增长v[i]，如果v[i]无法增长，我们可以将它剔出，赋值为-1。那么如何增长就是一大问题（其实这一题的关键就在此）。我们有两类增长方式：
1． 对于v[i]，如果v[i+v[i]]不为-1,那么可以将其赋值到v[i]，而将v[i+v[i]]赋值为-1（v[i]已经包含它的信息，v[i+v[i]]已经没有利用价值——poor v[i+v[i]]！！！）。我们每次选择最大的v[i+v[i]]来进行操作，比他小的可以忽略（有时会受到鄙视，就像我）。原因在于，对于每一个v[i+v[i]]，从头到尾增长机会是均等的，在当前的数比较小是他对应的序列比较小的缘故，因此应当被鄙视。在不断的淘汰中剩下一个即为所求，就是此题的思想。
2． 但是不是所有时候都会存在可以使用的v[i+v[i]]，比如一开始我们付所有的v[i]为0，那么第一次调节时，maxnum=0，按么此时是无法增长的，因此我们应该找最小的字母来增加到v[i]中，方法即为找到所有s[i+v[i]]中最小的那个字母，然后把v[i]强行加1，以此来更新。当然，条件是v[i]<>-1。
实现时，我们用数组l1记录当前可用的v[i]的i值，然后不断更新，更新时用l2临时记录更新情况，如此下去直到剩下的有效v[i]只有一个。