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

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

2、題引入有兩條環(huán)狀的項(xiàng)鏈，每條項(xiàng)鏈上各有n個(gè)多種顏色的珍珠，相同顏色的珍珠，被視為相同。問題：判斷兩條項(xiàng)鏈?zhǔn)欠裣嗤：?jiǎn)單分析：由于項(xiàng)鏈?zhǔn)黔h(huán)狀的，因此循環(huán)以后的項(xiàng)鏈被視為相同的，如圖的兩條項(xiàng)鏈就是一樣的。ioi2003冬令營(yíng)演示文稿安徽周源明確幾個(gè)記號(hào)和概念|s|=length(s)，即s的長(zhǎng)度。1ij|s|s串：si為s的第i個(gè)字符。sij=copy(s,i,j-i+1)。 這里1 i j |s|。sijioi2003冬令營(yíng)演示文稿安徽周源明確幾個(gè)記號(hào)和概念定義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冬令營(yíng)演示文稿安徽周源明確幾個(gè)記號(hào)和概念如果字符串s1可以經(jīng)過有限次循環(huán)得到s2，則稱s1和s2是循環(huán)同構(gòu)的。例如：s1和s2是循環(huán)同構(gòu)的！s1=a b c db c d a一次循環(huán)s2=c d a b一次循環(huán)ioi2003冬令營(yíng)演示文稿安徽周源明確幾個(gè)記號(hào)和概念設(shè)有兩個(gè)映射f1，f2:aa， 定義f1和f2的連接f1f2(x)=f1(f2(x)。ioi2003冬令營(yíng)演示文稿安徽周源問題的數(shù)學(xué)語言表達(dá)形式給定兩個(gè)長(zhǎng)度相等的字符串，|s1|=|s2|，判斷它們是否是循環(huán)同構(gòu)的。ioi2003冬令營(yíng)演示文稿安徽周源枚舉算法易知，s1的不同的循環(huán)串最多

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

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

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

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

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

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

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

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

12、可能是s1的最小表示！因此m(s1)i+k，指針i滑到ui+k+1處仍可以保證小于等于m(s1)！ioi2003冬令營(yíng)演示文稿安徽周源“最小表示法”在本題的應(yīng)用同理，當(dāng)ui+kwj+k的時(shí)候，可以將指針j滑到wj+k+1處！也就是說，兩指針向后滑動(dòng)比較失敗以后，指向較大字符的指針向后滑動(dòng)k+1個(gè)位置。下面讓我們將這種方法應(yīng)用于一個(gè)實(shí)例。ioi2003冬令營(yíng)演示文稿安徽周源“最小表示法”在本題的應(yīng)用設(shè)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比較失敗時(shí)k=1不相等因?yàn)閡i+kwj+k所以移動(dòng)指針iji比較失敗時(shí)k

13、=0ioi2003冬令營(yíng)演示文稿安徽周源“最小表示法”在本題的應(yīng)用設(shè)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不相等因?yàn)閡i+kwj+k所以移動(dòng)指針ijii比較失敗時(shí)k=2ioi2003冬令營(yíng)演示文稿安徽周源“最小表示法”在本題的應(yīng)用設(shè)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)同構(gòu)的！ ioi2003冬令營(yíng)演示文稿安徽周源“最小表示法”在本題的應(yīng)用在這個(gè)例子中，算法正確出解。算法的具體描述和證明請(qǐng)同學(xué)

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