Posted on 2011-04-23 16:09
Mato_No1 阅读(540)
评论(1) 编辑 收藏 引用 所属分类:
经典问题的模型 、
字符串匹配
【问题描述】
给出一个环形的字符串S，长度为N，现在要找到一个断开点，使得从这里断开后的字符串字典序最小。或者说，对于长度为N的字符串S[0..N-1]，找到一个位置i，使得字符串S' = S[i..N-1] + S[0..i-1]的字典序最小。若存在多个这样的最优断点，则取最左边(i最小)的那个。
【Sample Input】
amandamanda
【Sample Output】
10
（从第10位断开后得到的字符串"aamandamand"的字典序是11个断开位置中最小的）
【分析】
首先将这个环形串拆开：只需将S[0..N-1]的后面再接上S[0..N-2]即可（如对于样例，可构造字符串T = "amandamandaamandamand"），则T的任意一个长度为N的子串T[i..i-N+1]就是S从第i位断开得到的字符串。此时问题就变成了：给出一个长度为(2N-1)的字符串，求出其所有长度为N的子串中字典序最小的。
设F[x]为T中所有起始位小于N的长度为x的子串中字典序最小的子串的起始位（若有多个则取最左边的），如对于T="abaabaaababaabaaa"，有F[0]=F[1]=0，F[2]=2，F[3]=F[4]=5……本题的目的就是求出F[N]的值。一开始已知的只有F[0]=0（长度为0的字符串都是空串，字典序都是最小的，取最左边的第0位）。
可以发现，F数组有很多重要的性质：
性质1 F[0..N]数组是单调递增的。
证明：用反证法。设存在一个值x(0<=x<N)使得F[x]>F[x+1]则根据定义，有T[F[x+1]..F[x+1]+x]<=T[F[x]..F[x]+x]（这里一定不会越界，即F[x]+x的值一定不大于(2N-1)，因为x<N，又根据得F[x]<N，故F[x]+x<2N），这样，必有T[F[x+1]..F[x+1]+x-1]<=T[F[x]..F[x]+x-1]。然而根据F[x]的定义又可以得到T[F[x+1]..F[x+1]+x-1]>T[F[x]..F[x]+x-1]（否则F[x]的值就应该等于F[x+1]的值了），矛盾，故在F[0..N]中不可能存在任何F[x]>F[x+1]的情况，也即F[0..N]数组是单调递增的（以下将F[0..N]数组简称为F数组）。
性质2 对于任意值x(0<=x<N)，必然满足F[x+1]=F[x]或F[x+1]>F[x]+x。
证明：因为前面已经证明了F数组是单调递增的，这里只需证明对于任意x(0<=x<N)，不存F[x]<F[x+1]<=F[x]+x的情况即可。
这里同样用反证法。设存在一个值x(0<=x<N)使得F[x]<F[x+1]<=F[x]+x。则根据定义有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]。设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[x]的值就应该是(F[x]+2D)了，这显然不可能。所以，一开始假设的这种情况是不可能存在的，即对于任意值x（0<=x<N），必然满足F[x+1]=F[x]或F[x+1]>F[x]+x。
根据F数组的以上两个性质可以设计出本题的算法：
设目前已经求出了F[0..x-1]的值，且F[x-1]=i。首先将T[0..i-1]全部删去（因为F数组是单调递增的，F[x]的值一定不小于i），然后对T自身作扩展KMP（就是以T为模板串，T为子串的扩展KMP，相当于其预处理部分），一开始先将F[x]置为i，设第j位的匹配长度为next[j]，若next[j]=x-1且T[j+x-1]<T[i+x-1]，则将F[x]的值改为j，这样扫描一遍，即求出了F[x]的值。若扫描过程中未出现任何next[j]=x-1，则设所有next[j]值不小于x的最小next[j]值为y，则可以直接得到F[x..y-1]的值均等于F[x-1]。就这样直到求出F[N]的值为止。
时间复杂度：O(NÖN)，可以根据性质2得到。