二分法求解原理（轉）
設當前串為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]只有一個。