算法合集之淺析“最小表示法”思想在字符串循環(huán)同構問題中的應用

1、ioi2003冬令營演示文稿安徽周源淺析“最小表示法”思想在字符串循環(huán)同構問題中的應用安徽省蕪湖市第一中學周 源 ioi2003冬令營演示文稿安徽周源前言“最小表示法最小表示法”比起動態(tài)規(guī)劃、貪心等思想，比起動態(tài)規(guī)劃、貪心等思想，在當今競賽中似乎并不是很常見。但是在當今競賽中似乎并不是很常見。但是在解決判斷在解決判斷“同構同構”一類問題中卻起著一類問題中卻起著重要的作用。重要的作用。本文即將討論字符串中的同構問題，如何本文即將討論字符串中的同構問題，如何巧妙地運用最小表示法來解題呢，讓我巧妙地運用最小表示法來解題呢，讓我們繼續(xù)一起思考吧。們繼續(xù)一起思考吧。ioi2003冬令營演示文稿安徽周源問

2、題引入有兩條環(huán)狀的項鏈，每條項鏈上各有n個多種顏色的珍珠，相同顏色的珍珠，被視為相同。問題：判斷兩條項鏈是否相同。簡單分析：由于項鏈是環(huán)狀的，因此循環(huán)以后的項鏈被視為相同的，如圖的兩條項鏈就是一樣的。ioi2003冬令營演示文稿安徽周源明確幾個記號和概念|s|=length(s)，即s的長度。1ij|s|s串：si為s的第i個字符。sij=copy(s,i,j-i+1)。 這里1 i j |s|。sijioi2003冬令營演示文稿安徽周源明確幾個記號和概念定義s的一次循環(huán)s(1)=s2|s|+s1； s的k次循環(huán)(k1)s(k)為s(k-1)的一次循環(huán)； s的0次循環(huán)s(0)=s。12ij|s

3、|s串：12ij|s|s(1)串：ioi2003冬令營演示文稿安徽周源明確幾個記號和概念如果字符串s1可以經(jīng)過有限次循環(huán)得到s2，則稱s1和s2是循環(huán)同構的。例如：s1和s2是循環(huán)同構的！s1=a b c db c d a一次循環(huán)s2=c d a b一次循環(huán)ioi2003冬令營演示文稿安徽周源明確幾個記號和概念設有兩個映射f1，f2:aa， 定義f1和f2的連接f1f2(x)=f1(f2(x)。ioi2003冬令營演示文稿安徽周源問題的數(shù)學語言表達形式給定兩個長度相等的字符串，|s1|=|s2|，判斷它們是否是循環(huán)同構的。ioi2003冬令營演示文稿安徽周源枚舉算法易知，s1的不同的循環(huán)串最多

4、只有|s1|個，即s1,s1(1),s1(2),s1(|s1|-1)，所以只需要把他們一一枚舉，然后分別與s2比較即可。ioi2003冬令營演示文稿安徽周源枚舉算法優(yōu)點：思維簡單，易于實現(xiàn)。時間復雜度是o(n2)級（n=|s1|=|s2|）。如果n大一些，幾十萬，幾百萬time limit exceeded!ioi2003冬令營演示文稿安徽周源構造新的算法首先構造新的模型：s=s1+s1為主串，s2為模式串。如果s1和s2是循環(huán)同構的，那么s2就一定可以在s中找到匹配！ioi2003冬令營演示文稿安徽周源匹配算法：理論的下界在s中尋找s2的匹配是有很多o(n)級的算法的。本題最優(yōu)算法的時空復雜

5、度均為o(n)級。這已經(jīng)是理論的下界了。ioi2003冬令營演示文稿安徽周源小結：枚舉和匹配算法很容易得到的枚舉算法顯然不能滿足大數(shù)據(jù)的要求，于是我們從算法的執(zhí)行過程入手，探查到了枚舉算法的實質(zhì)：模式匹配。最后，通過巧妙的構造、轉換模型，直接套用模式匹配算法，得到了o(n)級的算法。ioi2003冬令營演示文稿安徽周源探索新的算法但是問題是否已經(jīng)完美解決了呢？ kmp算法的缺點：難理解，難記憶；可擴展性不強。ioi2003冬令營演示文稿安徽周源引例有兩列數(shù)a1,a2an和b1,b2bn ，不記順序，判斷它們是否相同。 an：4 2 6 3bn：6 2 3 4相同的兩列數(shù)ioi2003冬令營演示

6、文稿安徽周源分析由于題目要求“不記順序”，因此每一列數(shù)的不同形式高達n!種之多！如果要一一枚舉，顯然是不科學的。如果兩列數(shù)是相同的，那么將它們排序之后得到的數(shù)列一定也是相同的。 an：4 2 6 3bn：6 2 3 4排序后an：2 3 4 6bn：2 3 4 6相同ioi2003冬令營演示文稿安徽周源小結：引例這道題雖然簡單，卻給了我們一個重要的啟示：當某兩個對象有多種表達形式，且需要判斷它們在某種變化規(guī)則下是否能夠達到一個相同的形式時，可以將它們都按一定規(guī)則變化成其所有表達形式中的最小者，然后只需要比較兩個“最小者”是否相等即可！ ioi2003冬令營演示文稿安徽周源定義：“最小表示法”設

7、有事物集合t=t1，t2，tn， 映射集合f=f1，f2，fm。任意ff均為t到t的映射，fi:tt。如果兩個事物s,t t，有一系列f的映射的連接fi1fi2fik(s)=t，則說s和t是f本質(zhì)相同的。ioi2003冬令營演示文稿安徽周源定義：“最小表示法”其中f滿足兩個條件：任意tt，一定能在f中一系列映射的連接的作用下，仍被映射至t。即任意一個事物tt，它和自己是f本質(zhì)相同的。 任意s,tt，若在f的一系列映射作用下，s和t是f本質(zhì)相同的。那么一定有另一系列屬于f的映射作用下，t和s是f本質(zhì)相同的。即“本質(zhì)相同”這個概念具有自反性。即“本質(zhì)相同”這個概念具有對稱性。ioi2003冬令營演

8、示文稿安徽周源定義：“最小表示法”另外，根據(jù)“本質(zhì)相同”概念的定義很容易知道，“本質(zhì)相同”這個概念具有傳遞性。即若t1和t2是f本質(zhì)相同，t2和t3是f本質(zhì)相同，那么一定有t1和t3是本質(zhì)相同的。ioi2003冬令營演示文稿安徽周源定義：“最小表示法”給定t和f，如何判斷t中兩個事物s和t是否互為f本質(zhì)相同呢？ “最小表示法”就是可以應用于此類題目的一種思想： 確立一種t中事物的大小關系根據(jù)f中的變化規(guī)則 將s和t化成規(guī)定大小關系中的最小者m1和m2如果m1=m2s本質(zhì)相同m1本質(zhì)相同m2本質(zhì)相同tm1m2可以證明，s和t不是本質(zhì)相同ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應

9、用在本題中，事物集合表示的是不同的字符串，映射集合則表示字符串的循環(huán)法則,“事物中的大小關系”就是字符串間的大小關系。 分別求出s1和s2的最小表示比較它們是否相同最直接最簡單的方法：ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用如m(bbbaab)=4設函數(shù)m(s)返回值意義為：從s的第m(s)個字符引起的s的一個循環(huán)表示是s的最小表示。若有多個值，則返回最小的一個?，F(xiàn)在換一種思路：s=b b b a a bioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用現(xiàn)在換一種思路：1 |s1|s1:1 |s2|s2:u:w:1|s1| |s1|+1 2*|s1|1|s2|

10、 |s2|+1 2*|s2|設u=s1+s1，w=s2+s2并設指針i,j指向u,w第一個字符ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用u:1 m(s1) 2*|s1|w:1 m(s2) 2*|s2|ij現(xiàn)在換一種思路：如果s1和s2是循環(huán)同構的，那么當i,j分別指向m(s1),m(s2)時，一定可以得到uii+|s1|-1=wjj+|s2|-1，迅速輸出正確解。|s1|s2|ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用現(xiàn)在換一種思路：同樣s1和s2循環(huán)同構時，當i,j分別滿足im(s1),jm(s2)時，兩指針仍有機會達到i=m(s1),j=m(s2)這

11、個狀態(tài)。問題轉化成，兩指針分別向后滑動比較，如果比較失敗，如何正確的滑動指針，新指針i,j仍然滿足im(s1),jm(s2)ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用設指針i,j分別向后滑動k個位置后比較失敗(k0)，即有ui+kwj+k1iu：i+ki+k+1|s1|1w：jj+kj+k+1|s2|大于當ixi+k時，我們來研究s1(x-1)。x設ui+kwj+k，同理可以討論ui+kwj+(x-i)j+k。1ixu：i+ki+k+1|s1|1w：jj+(x-i)j+kj+k+1|s2|大于s1(x-1)的前幾個字符一定是s1的其他循環(huán)表示的前幾個字符所以s1(x-1)不

12、可能是s1的最小表示！因此m(s1)i+k，指針i滑到ui+k+1處仍可以保證小于等于m(s1)！ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用同理，當ui+kwj+k的時候，可以將指針j滑到wj+k+1處！也就是說，兩指針向后滑動比較失敗以后，指向較大字符的指針向后滑動k+1個位置。下面讓我們將這種方法應用于一個實例。ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用設s1=babba，s2=bbaba。 u=b a b b a b a b b aw=b b a b a b b a b aij比較失敗時k=1不相等因為ui+kwj+k所以移動指針iji比較失敗時k

13、=0ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用設s1=babba，s2=bbaba。u=b a b b a b a b b aw=b b a b a b b a b a不相等因為ui+kwj+k所以移動指針ijii比較失敗時k=2ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用設s1=babba，s2=bbaba。u=b a b b a b a b b aw=b b a b a b b a b ajiu59=w37！所以s1和s2是循環(huán)同構的！ ioi2003冬令營演示文稿安徽周源“最小表示法”在本題的應用在這個例子中，算法正確出解。算法的具體描述和證明請同學

14、們自行完成，這里不再贅述。ioi2003冬令營演示文稿安徽周源小結：“最小表示法”思想經(jīng)過努力，我們終于找到了一個與匹配算法本質(zhì)不同的線性算法。 比較點匹配算法“最小表示法”思想時間復雜度o(n)級同樣優(yōu)秀的線性算法輔助空間記錄next數(shù)組o(n)級只需要記錄兩個指針常數(shù)級別算法實現(xiàn)難懂，難記憶簡潔，便于記憶可擴展性受next數(shù)組嚴重制約很強ioi2003冬令營演示文稿安徽周源總結“最小表示法”是判斷兩種事物本質(zhì)是否相同的一種常見思想，它的通用性也是被人們認可的無論是搜索中判重技術，還是判斷圖的同構之類復雜的問題，它都有著無可替代的作用。仔細分析可以得出，其思想精華在于引入了“序”這個概念，從而將紛繁的待處理對象化為單一的形式，便于比較?！白钚”硎痉ā彼枷霊门兄丶夹g判斷圖的同構同構類問題單一的形式有序化ioi2003冬令營演示文稿安徽周源總結然而值得注意的是，在如今的信息學競賽中，試題紛繁復雜，使用的算法也不再拘泥于幾個經(jīng)典的算法，改造經(jīng)典算法或是將多種算法組