• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            bon

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            之前一篇KMP講的是直接的應用,這一篇將借助兩道相似的POJ題目對next數組進行深入一些的討論。
            兩道題目分別是:POJ 1961 2406,題意是給出一個串s,找出這個能表示成某個字串A的K次聯接,即s=[A...A] (K個A),要求K最大,即A最小。
            暴力可以過2406,但1961沒法過,超時。

            看了discuss的討論,只要計算KMP算法中的next數組,判斷n (串長)能否被d = n-1-next[n-1] (即最后一個next)整除,若能,則s是s[next[n-1]...n-1]的n/d聯接。具體細節沒有證明。

            下面給出我的一些想法,為什么以上判斷是正確的。
            首先,若s可以表示成[A...A],則next數組確實是符合以上整除的要求的,且從0到next[n-1]這個proper prefix (見上一篇KMP文章的定義)是s的最長的proper suffix。

            其次,為什么d整除n,就能斷定s是s[next[n-1]+1...n-1]的n/d次聯接呢?
            1) 用文字表述太麻煩,用下圖說明
             
            圖中顏色一致的段是一樣的(這是因為下面那段是上面那段的proper prefix),即上面的1等于下面的1,而由于下面的段是上面段的proper prefix,因此下面的1又等于上面的2,所以上面的1跟2是相等的。以此類推,上面的小段都是相等的。
            posted on 2008-07-31 10:51 bon 閱讀(307) 評論(0)  編輯 收藏 引用 所屬分類: Programming Contest
            Google PageRank 
Checker - Page Rank Calculator
            久久人妻少妇嫩草AV无码专区 | 97久久久久人妻精品专区 | 久久精品国产亚洲αv忘忧草| 亚洲国产精品狼友中文久久久 | 91精品国产91久久久久久青草 | 亚洲国产视频久久| 久久精品国产亚洲AV高清热| 狠狠久久亚洲欧美专区| 婷婷久久综合| 青青青青久久精品国产h| 青青久久精品国产免费看| 久久精品www人人爽人人| 久久伊人色| 伊人丁香狠狠色综合久久| 伊人色综合久久天天人手人婷| 欧美综合天天夜夜久久| 日韩久久久久久中文人妻| 亚洲国产成人久久一区久久| 丁香五月网久久综合| 久久久久国产精品嫩草影院| 蜜桃麻豆www久久国产精品| 国产精品久久午夜夜伦鲁鲁| 久久精品国产99久久久古代| 久久精品无码av| 久久精品嫩草影院| 久久99国产综合精品免费| 狠狠色丁香婷婷久久综合| 国内精品久久久久国产盗摄| 日韩AV无码久久一区二区| 久久综合伊人77777| 精品人妻伦九区久久AAA片69 | 国内精品伊人久久久久av一坑| 久久天天躁狠狠躁夜夜2020老熟妇 | 嫩草影院久久国产精品| 72种姿势欧美久久久久大黄蕉| 久久国产欧美日韩精品免费| 久久夜色撩人精品国产| 亚洲国产香蕉人人爽成AV片久久| 久久影视综合亚洲| 国内精品久久久久影院老司| 久久精品免费全国观看国产|