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