二分法求解原理（轉）
設當前串為s[l..r] 則s[l..r]的最小位置來自于s[l,mid]（記為A） s[mid+1,r]（記為B）的最小位置
現(xiàn)在只要將A B 中較優(yōu)的可以作為s[l...r]的最優(yōu)值。
比較A B的方法 比較s[A..B-1]與S[B..T]這二個長度相等的串
1.若串S[A..B-1]小于串S[B..T]，那么A必優(yōu)于B。
2.若串S[A..B-1]大于串S[B..T]，那么B必優(yōu)于A。
3.若串S[A..B-1]等于串[B..T]，分情況討論：（設從A開始的長度為N的串為S1，B開始的長度為N的串為S2）
1）若S1<S2 那么 A較優(yōu)
2）若S1=S2那么 A也較優(yōu)（A的位置靠前）
3）若S1>S2那么 T+1..len中有一個位置K 比 A與B 優(yōu)，此時選A選B無影響//實際上如果滿足這個條件,則最優(yōu)值必然在這兩個區(qū)間外，因為從s[t+1]開始的字符串跟s[b]開始的字符串一樣！
綜上所述，當S[A..B-1]=S[B..T]時，選A
usaco官方題解（轉）
v[i]表示，從i開始的v[i]長度是所有v[i]長度中最小的。我們把讀入的s變?yōu)?span>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]已經(jīng)包含它的信息，v[i+v[i]]已經(jīng)沒有利用價值——poor v[i+v[i]]！！！）。我們每次選擇最大的v[i+v[i]]來進行操作，比他小的可以忽略（有時會受到鄙視，就像我）。原因在于，對于每一個v[i+v[i]]，從頭到尾增長機會是均等的，在當前的數(shù)比較小是他對應的序列比較小的緣故，因此應當被鄙視。在不斷的淘汰中剩下一個即為所求，就是此題的思想。
2． 但是不是所有時候都會存在可以使用的v[i+v[i]]，比如一開始我們付所有的v[i]為0，那么第一次調節(jié)時，maxnum=0，按么此時是無法增長的，因此我們應該找最小的字母來增加到v[i]中，方法即為找到所有s[i+v[i]]中最小的那個字母，然后把v[i]強行加1，以此來更新。當然，條件是v[i]<>-1。
實現(xiàn)時，我們用數(shù)組l1記錄當前可用的v[i]的i值，然后不斷更新，更新時用l2臨時記錄更新情況，如此下去直到剩下的有效v[i]只有一個。