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

淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用 安徽 周源淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用安徽省蕪湖市第一中學周源【目錄】淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用1【目錄】1【摘要】2【關(guān)鍵字】2【正文】31、 問題引入31. 明確幾個記號和概念32. 問題32、 枚舉算法和匹配算法31. 枚舉算法32. 匹配算法33. 小結(jié)43、 最小表示法思想41. “最小表示法”思想的提出42. “最小表示法”思想的定義43. “最小表示法”在本題的應(yīng)用54. 模擬算法執(zhí)行75. 小結(jié)84、 總結(jié)8淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用 安徽 周源【摘要】最小表示法在搜索判重、判斷圖的同構(gòu)等很多問題中有著重要的應(yīng)用。本文就圍繞字符串循環(huán)同構(gòu)的判斷這個問題，在很容易找到O(N)的匹配后，本文引進的“最小表示法”思想，并系統(tǒng)的對其下了定義，最后利用“最小表示法”思想構(gòu)造出了更優(yōu)秀，更自然的算法。無論是增加“最小表示法”思想這方面的知識，提高增加競賽中的綜合素質(zhì)，相信本文對同學們還是有所裨益的?！娟P(guān)鍵字】字符串 循環(huán)同構(gòu) 匹配 最小表示法淺析“最小表示法”思想在字符串循環(huán)同構(gòu)問題中的應(yīng)用 安徽 周源【正文】1、 問題引入1. 明確幾個記號和概念由于本篇論文主要討論與字符串有關(guān)的算法，所以在本文中，一切未經(jīng)說明的以開頭的變量均表示字符串。，即的長度。為的第個字符。這里。，即截取出的第個字符到第個字符的子串。這里。特別的，。定義的一次循環(huán)；而的次循環(huán)，的零次循環(huán)。如果字符串可以經(jīng)過有限次循環(huán)得到，即有，則稱和是循環(huán)同構(gòu)的。設(shè)有兩個映射，定義和的連接，這里。這個定義用于后文算法描述中。2. 問題給定兩個字符串和，判斷他們是否循環(huán)同構(gòu)。2、 枚舉算法和匹配算法1. 枚舉算法很容易知道，的不同的循環(huán)串最多只有個，即，所以只需要把他們一一枚舉，然后分別與比較即可。枚舉算法思維簡單，易于實現(xiàn)，而它的時間復雜度是級這里N=|s1|=|s2|。，已經(jīng)可以勝任大多數(shù)問題的要求了。然而如果大至幾十萬，幾百萬，枚舉算法就無能為力了，有沒有更優(yōu)秀的算法呢？2. 匹配算法從枚舉算法執(zhí)行過程中很容易發(fā)現(xiàn)，枚舉算法的本質(zhì)就是在一個可以循環(huán)的字符串中尋找的匹配，于是聯(lián)想到模式匹配的改進算法是級的，那么在循環(huán)串中尋找匹配是不是也有線性的算法呢？回答是肯定的：由于循環(huán)串與一般的字符串本質(zhì)的區(qū)別就是前者是“循環(huán)”的，如果能去掉“循環(huán)”這個限制，那么就可以直接套用一般字符串的模式匹配算法了！顯然，將復制兩次：做為主串，則任何與循環(huán)同構(gòu)的字符串至少都可以在中出現(xiàn)一次，于是可以說就是循環(huán)串的一般字符串形式！問題成功轉(zhuǎn)化為求在中的模式匹配。這完全可以在級時間內(nèi)解決。3. 小結(jié)很容易得到的枚舉算法顯然不能滿足大數(shù)據(jù)的要求，于是我們從算法的執(zhí)行過程入手，探查到了枚舉算法的實質(zhì)：模式匹配。最后，通過巧妙的構(gòu)造、轉(zhuǎn)換模型，直接套用模式匹配算法，得到了級別的算法。但是問題是否已經(jīng)完美解決了呢？也許你會說：以KMP算法為首的模式匹配改進算法，都是以難理解，難記憶著稱的！這的確是KMP算法的缺點，而且其next數(shù)組繁瑣的計算嚴重制約著算法的可擴展性，看來是有必要尋求更簡潔的算法了。3、 最小表示法思想1. “最小表示法”思想的提出首先來看一個引例：引例有兩列數(shù)，和，不記順序，判斷它們是否相同。分析由于題目要求“不記順序”，因此每一列數(shù)的不同形式高達種之多！如果要一一枚舉，顯然是不科學的。于是一種新的思想提出了：如果兩列數(shù)是相同的，那么將它們排序之后得到的數(shù)列一定也是相同的。于是，算法復雜度迅速降為級。這道題雖然簡單，卻給了我們一個重要的啟示：當某兩個對象有多種表達形式，且需要判斷它們在某種變化規(guī)則下是否能夠達到一個相同的形式時，可以將它們都按一定規(guī)則變化成其所有表達形式中的最小者，然后只需要比較兩個“最小者”是否相等即可！下面我們系統(tǒng)的給出“最小表示法”思想的定義。2. “最小表示法”思想的定義設(shè)有事物集合和映射集合，其中是到的映射：。如果兩個事物，有一系列映射的連接使，則說和是本質(zhì)相同的。這里滿足：任意，一定能在中一系列映射的連接的作用下，仍被映射至。任意，若有使，則一定存在一個或一系列映射，他們的連接。由的性質(zhì)可知，和是本質(zhì)相同的，即“本質(zhì)相同”這個概念具有自反性。從性質(zhì)可知，如果和是本質(zhì)相同的，那么和也一定是本質(zhì)相同的。即“本質(zhì)相同”這個概念具有對稱性。另外，根據(jù)“本質(zhì)相同”概念的定義很容易知道，“本質(zhì)相同”這個概念具有傳遞性。即若和是本質(zhì)相同，和是本質(zhì)相同，那么一定有和是本質(zhì)相同的。給定和，如何判斷中的兩個事物和是否互為本質(zhì)相同的呢？“最小表示法”就是可以應(yīng)用于此類題目的一種思想。它規(guī)定中的所有事物均有一種特殊的大小關(guān)系。然后，根據(jù)中的變化規(guī)則，將和均化為規(guī)定大小關(guān)系中的最小者和，如果兩者相同，則易知，和本質(zhì)相同，和本質(zhì)相同，和本質(zhì)相同，所以和是本質(zhì)相同的。否則，可以證明，和不是本質(zhì)相同的。3. “最小表示法”在本題的應(yīng)用在本題中，事物集合表示的是不同的字符串，而映射集合則表示字符串的循環(huán)法則，“事物中的大小關(guān)系”就是字符串間的大小關(guān)系。那么，如何將最小表示法應(yīng)用于本題呢？最簡單的方法就是根據(jù)上文，分別求出和的最小表示，比較它們是否相同。如果要是很簡單的這么做，問題就非常麻煩了：求字符串的最小表示法雖然有級算法，但是思路十分復雜，還不如匹配算法如果單純得這么做，就違背了我們尋找更好算法的初衷。這樣，看上去“最小表示法”是無能為力了。然而我們換一種思路：和匹配算法相似，將和各復制一次：，；并設(shè)兩個指針和分別指向和的第一個字符。設(shè)，也就是說函數(shù)返回的是最小表示串的第一個字符在原串中的位置注意，這里所說的“在原串中的位置”，并不是單純的在原串中尋找到的第一個匹配，而是以之開頭的循環(huán)串是原串的最小表示。，如果有多個最小表示串，則取在原串中位置最小的一個。顯然如果和是循環(huán)同構(gòu)的，且當前兩指針且的時候，一定可以得到，迅速得到和是循環(huán)同構(gòu)的。當且時，兩指針仍然有機會達到,這個狀態(tài)。于是問題轉(zhuǎn)化成：仍然設(shè)和是循環(huán)同構(gòu)的，當前兩指針分別向后滑動比較，如果發(fā)現(xiàn)比較失敗，有，如何向后滑動指針，使新指針仍然滿足和仍然滿足。u串：ixi+ki(i+k+1)|s1|w串：jj+(x-i)j+kj+k+1|s2|相等大于從不相等的和下手：如果，那么任意整數(shù)，從第個字符開頭的循環(huán)串是，如圖，的前個字符是，當然，也可以表示為，對稱的，可以在串中找到一段字符，這兩段字符串長度相等，而且根據(jù)上文假設(shè)的掃描過程可以得到。而，所以得到，即。而根據(jù)假設(shè)和是循環(huán)同構(gòu)的，那么一定能在的所有循環(huán)串中找到一個字符串，滿足它的前個字符是。于是有，得一定不是的最小表示。所以不可能在一段中，也就可以將指針向后滑動個字符：。同理得到如果，可將指針向后滑動個字符：。仍滿足，。于是設(shè)計出算法：將和各復制一次：，；并設(shè)兩個指針和分別指向和的第一個字符。如果和均中至少一個大于，則可以肯定和不是循環(huán)同構(gòu)的，返回，算法結(jié)束；否則找到最小的使，如果這樣的不存在或，則說明，即和各有一段長為的子串相等，和是循環(huán)同構(gòu)的，返回，算法結(jié)束；否則轉(zhuǎn)第步。如果，則將指針向后滑動個字符：；否則說明，就將指針向后滑動個字符：。繼續(xù)執(zhí)行第步。容易得出，本算法的時空復雜度也是均為級。更清楚一點，我們附上一個例子：4. 模擬算法執(zhí)行設(shè)，顯然它們是循環(huán)同構(gòu)的。模擬執(zhí)行算法是這樣的：首先有，并設(shè)指針。第一次執(zhí)行、兩步：第一次執(zhí)行完畢后得到，下面第二次執(zhí)行：現(xiàn)在結(jié)果是，同理執(zhí)行第三次：此時已經(jīng)是，執(zhí)行第四次：這時發(fā)現(xiàn)！成功得出和是循環(huán)同構(gòu)的，算法返回值為真。5. 小結(jié)經(jīng)過一番努力，我們終于得到了一個與匹配算法本質(zhì)不同的線性算法。在這個問題中，“最小表示法”思想引導我們從問題的另一方面分析，進而構(gòu)造出一個全新的算法。比起匹配算法，它容易理解，便于記憶，實現(xiàn)起來，也不過是短短的幾重循環(huán)，非常方便，便于應(yīng)用于擴展問題。4、 總結(jié)“最小表示法”是判斷兩種事物本質(zhì)是否相同的一種常見思想，它的通用性也是被人們認可的無論是搜索中判重技術(shù)，還是判斷圖的同構(gòu)之類復雜的問題，它都有著無可替代的作用。深入分析不難得出，該思想的精華在于引入了“序”這個概念，將待比較兩個事物化為規(guī)定順序中最小的（也可能是最大的）再加以比較。然而值得注意的是，在如