• <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
            免费精品久久久久久中文字幕| 国内高清久久久久久| 99久久婷婷国产综合亚洲| 午夜精品久久久久久中宇| 国产一区二区三区久久| 色婷婷噜噜久久国产精品12p| 国内精品久久国产| 久久国产乱子精品免费女| 久久久久这里只有精品| 无码专区久久综合久中文字幕 | 亚洲色大成网站WWW久久九九| www久久久天天com| 一本久久精品一区二区| 2020久久精品国产免费| 亚洲乱码日产精品a级毛片久久| 狠狠88综合久久久久综合网| 欧美日韩成人精品久久久免费看| 久久精品无码专区免费东京热 | 色99久久久久高潮综合影院| 久久国产色AV免费观看| 2021国产精品午夜久久| 久久精品国产精品亚洲| 国产精品禁18久久久夂久| 综合久久一区二区三区 | 久久综合综合久久狠狠狠97色88| 久久狠狠爱亚洲综合影院| 国产巨作麻豆欧美亚洲综合久久 | 久久精品国产2020| 亚洲国产天堂久久综合| 精品久久久久久99人妻| 国产精品久久网| 亚洲AV日韩精品久久久久| 久久人与动人物a级毛片| 少妇被又大又粗又爽毛片久久黑人| 国产精品成人99久久久久| 国产精品久久久久久一区二区三区| 久久精品中文无码资源站| 久久免费的精品国产V∧| 久久99精品国产自在现线小黄鸭 | 亚洲AV日韩精品久久久久久| 欧美黑人激情性久久|