Mato is No.1

【問題描述】
給出一個環(huán)形的字符串S，長度為N，現(xiàn)在要找到一個斷開點，使得從這里斷開后的字符串字典序最小。或者說，對于長度為N的字符串S[0..N-1]，找到一個位置i，使得字符串S' = S[i..N-1] + S[0..i-1]的字典序最小。若存在多個這樣的最優(yōu)斷點，則取最左邊(i最小)的那個。
【Sample Input】
amandamanda
【Sample Output】
10
（從第10位斷開后得到的字符串"aamandamand"的字典序是11個斷開位置中最小的）

【分析】
首先將這個環(huán)形串拆開：只需將S[0..N-1]的后面再接上S[0..N-2]即可（如對于樣例，可構(gòu)造字符串T = "amandamandaamandamand"），則T的任意一個長度為N的子串T[i..i-N+1]就是S從第i位斷開得到的字符串。此時問題就變成了：給出一個長度為(2N-1)的字符串，求出其所有長度為N的子串中字典序最小的。

設(shè)F[x]為T中所有起始位小于N的長度為x的子串中字典序最小的子串的起始位（若有多個則取最左邊的），如對于T="abaabaaababaabaaa"，有F[0]=F[1]=0，F(xiàn)[2]=2，F(xiàn)[3]=F[4]=5……本題的目的就是求出F[N]的值。一開始已知的只有F[0]=0（長度為0的字符串都是空串，字典序都是最小的，取最左邊的第0位）。

可以發(fā)現(xiàn)，F(xiàn)數(shù)組有很多重要的性質(zhì)：
性質(zhì)1 F[0..N]數(shù)組是單調(diào)遞增的。
證明：用反證法。設(shè)存在一個值x(0<=x<N)使得F[x]>F[x+1]則根據(jù)定義，有T[F[x+1]..F[x+1]+x]<=T[F[x]..F[x]+x]（這里一定不會越界，即F[x]+x的值一定不大于(2N-1)，因為x<N，又根據(jù)得F[x]<N，故F[x]+x<2N），這樣，必有T[F[x+1]..F[x+1]+x-1]<=T[F[x]..F[x]+x-1]。然而根據(jù)F[x]的定義又可以得到T[F[x+1]..F[x+1]+x-1]>T[F[x]..F[x]+x-1]（否則F[x]的值就應(yīng)該等于F[x+1]的值了），矛盾，故在F[0..N]中不可能存在任何F[x]>F[x+1]的情況，也即F[0..N]數(shù)組是單調(diào)遞增的（以下將F[0..N]數(shù)組簡稱為F數(shù)組）。
性質(zhì)2 對于任意值x(0<=x<N)，必然滿足F[x+1]=F[x]或F[x+1]>F[x]+x。
證明：因為前面已經(jīng)證明了F數(shù)組是單調(diào)遞增的，這里只需證明對于任意x(0<=x<N)，不存F[x]<F[x+1]<=F[x]+x的情況即可。
這里同樣用反證法。設(shè)存在一個值x(0<=x<N)使得F[x]<F[x+1]<=F[x]+x。則根據(jù)定義有T[F[x+1]..F[x+1]+x]<T[F[x]..F[x]+x]且T[F[x]..F[x]+x-1]<=T[F[x+1]..F[x+1]+x-1]，這樣必有T[F[x]..F[x]+x-1]=T[F[x+1]..F[x+1]+x-1]且T[F[x+1]+x]<T[F[x]+x]。設(shè)D=F[x+1]-F[x]，則T[F[x]]=T[F[x]+D]，因為D<=x，可得T[F[x]+D]=T[F[x]+2D]，即T[F[x]]=T[F[x]+2D]。這樣，T[F[x]..F[x]+x-D-1]=T[F[x]+2D..F[x]+x+D-1]；又因為T[F[x]+x-D]=T[F[x]+x]，而T[F[x+1]+x]（即T[F[x]+x+D]]）<T[F[x]+x]，這樣，T[F[x]+x+D]<T[F[x]+x-D]，也就是，T[F[x]+2D..F[x]+x+D]<T[F[x]..F[x]+x-D]！這樣可以得出，從(F[x]+2D)位開始的任意長度不小于(x-D)的子串，其字典序都小于從F[x]位開始的同樣長度的子串，由于F[x]<F[x+1]<=F[x]+x，D=F[x+1]-F[x]，所以有1<=D<=x，這樣，F(xiàn)[x]的值就應(yīng)該是(F[x]+2D)了，這顯然不可能。所以，一開始假設(shè)的這種情況是不可能存在的，即對于任意值x（0<=x<N），必然滿足F[x+1]=F[x]或F[x+1]>F[x]+x。

根據(jù)F數(shù)組的以上兩個性質(zhì)可以設(shè)計出本題的算法：
設(shè)目前已經(jīng)求出了F[0..x-1]的值，且F[x-1]=i。首先將T[0..i-1]全部刪去（因為F數(shù)組是單調(diào)遞增的，F(xiàn)[x]的值一定不小于i），然后對T自身作擴展KMP（就是以T為模板串，T為子串的擴展KMP，相當(dāng)于其預(yù)處理部分），一開始先將F[x]置為i，設(shè)第j位的匹配長度為next[j]，若next[j]=x-1且T[j+x-1]<T[i+x-1]，則將F[x]的值改為j，這樣掃描一遍，即求出了F[x]的值。若掃描過程中未出現(xiàn)任何next[j]=x-1，則設(shè)所有next[j]值不小于x的最小next[j]值為y，則可以直接得到F[x..y-1]的值均等于F[x-1]。就這樣直到求出F[N]的值為止。

時間復(fù)雜度：O(NÖN)，可以根據(jù)性質(zhì)2得到。