1、最小表示法最小表示法在解決判斷“同構”一類問題中有很大作用。循環同構問題：給出兩個串：si=“babba”和s2=“bbaba”，其中兩者均看成環狀的，即首尾是相接的，問：從si的哪里斷開可以得到和s2一樣的串或者兩者不會相同？本題就是從si的第2個字符a后面斷開，可以得到與s2一樣的串。這個問題就是同構問題。樸素算法(O(nm)：即嘗試si的n個斷開點，與s2進行比較，如果相同則找到同構位置，否則找不到。該算法僅適用于n,m規模較小情況，對于n,m都在10000規模的長度，明顯速度太慢。轉換為模式匹配：對于此類問題，已經有一個很好的轉換思路了，即：首先構造新的模型：S=s1+s1為主串，s2

2、為模式串。如果si和s2是循環同構的，那么s2就一定可以在S中找到匹配。否則找不到匹配則兩則不能同構。而在S中尋找s2的匹配是有很多O(N+M)級的算法了，KMP算法就是這樣一個優秀的算法，所以本問題轉換為模式匹配后應用KMP算法，可以在O(n+m)的時間內獲得問題的解。下面再來看看“最小表示法”在此類問題中的應用(算法思路來源于國家隊的一位隊員)，它也可以在O(n+n)時間內求解，更大的優勢還有無需KMP算法的Next數組，僅需要兩個指針即可。解析過程：問題：有兩列數ai,a2an和bi,b2bn，不記順序，判斷它們是否相同。eg：an=2,3,5,7；bn=2,7,53。一眼可見兩者是相同

3、的，但是對于計算機來說，如果采用枚舉算法，那么比較次數將是：n*(n-i)*(n-2).*2*i=n!量級。階乘增長之快，時間上是無法忍受的。抓住問題的本質：如果兩列數相同，那么它們排序之后從頭到尾肯定一樣！則問題在0(nlogn)時間解決。可見這個問題的本質就在于排序(非降序)之后的序列是原序列的“最小表示”，如果兩個序列的“最小表示”相同則兩者就相同，否則就不相同。啟示：當兩個對象有多種形式且需判斷它們在某種變換規則下是否相同時，可轉換為比較可以通過變換規則得到的所有表示的“最小表示”是否相同。例如本問題是不計順序的規則，最小表示就是非降序排列后的序列。當然對于其它問題就不能簡單的排序了，

4、需要滿足“在變換規則下可以達到的表示形式”。首先定義一個變換規則f判斷兩個事物s和t是否互為f本質相同，方法就是：將s，t轉換為規則f下的最小表示形式，再比較是否相同。返回到本節一開始提到的字符串循環同構問題，規則f就是“循環移動”，最直接最簡單的方法就是分別求出si,s2的最小表示，再比較兩者是否相同，但是可以發現這明顯也是一個0(n2)思路。換一種思路，令Min(s)返回值為：從s的第Min(s)個字符引起的s的一個循環表示的最小表示，若有多個值則返回下標最小的一個。例如s=bbbaab，那么Min(s)=3-下標從0算起。Min(s)的求法在后面部分具體闡述，這個問題僅僅用到這個概念，不

5、必直接求，因為當找到循環同構時實際就是Min(s)。先類似于模式匹配方法將兩者加倍：u=si+si，w=s2+s2,指針i，j分別指向u,w的第一個位置0,i，j指針滑動可以得到兩種情況：.若i,j分別指向Min(si)和Min(s2)時，一定有uii+|si|-i=wjj+|s2|+1也就是立馬得到解。2.否則i=Min(s1),j=Min(s2)時，兩指針仍然有希望到達i=Min(s1),j=Min(s2)這個狀態。因此問題轉換為：兩個指針分別向后滑動比較，如果比較失敗，如何正確的滑動指針使得新指針i,j仍然滿足：i=Min(s1),j=Min(s2)。設指針i,j分別向后滑動k個位置后比

6、較失敗(k=0),即有ui+k工wj+k。仍然分兩種情況：wj+k:令i=x=i+k時，我們來研究s1x-1,因為ux在ui的后x-i個位置,對應相等于在wj的后x-i個位置即wj+(x-i),同樣對應相等的ux+1=wj+(x+1-i)直至0 x=i+k-1，即有：uxx+i+k-1=wj+x-ij+x-1，現在已經在ui+k位置處不相等且ui+kwj+k，因此整個sx-1都不是si的最小表示的前綴，則Min(s1)i+k,所以i可以滑動到i+k+1仍可保證=Min(s1)。/*tju3275(WindysS),zju2006(GlassBeads),zju1729(HiddenPassword),hdu3374(StringProblem)*/#includeiostream#includestringusingnamespacestd;/*用最小表示法求字符串S的最小字典序返回字典序最小的串的首字母位置*/intMinRepresstation(stringS)inti=0,j=1,k=0;intlen=S.l