• <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>
            posts - 43,  comments - 9,  trackbacks - 0
            字符串少量習(xí)題小結(jié).

            spoj694(易) 后綴數(shù)組
            求一個字串的不同子串個數(shù).
            按rank考慮子串.加入子串S[i]時,獲得了len-Sa[i]個不同子串.但其中height[i]個已經(jīng)屬于S[i-1]了,所以實際子串?dāng)?shù)增加了len-Sa[i]-S[i-1]. 順序掃一遍height數(shù)組即得解.

            spoj687(中) 后綴數(shù)組
            求一個串的重復(fù)次數(shù)最多的連續(xù)重復(fù)子串.
            設(shè)周期為L的連續(xù)重復(fù)子串存在,則點0,L,2L,...,kL必能覆蓋到一個完整周期. 因此對L,考察這些點的字符相等情況,LCP情況,可得到L的解.
            枚舉L.
            復(fù)雜度是O(n/1+n/2+...+n/n) = O(nlogn)

            pku3693(中) 后綴數(shù)組
            同spoj687,只是結(jié)果還要輸出字典序最小的滿足條件的串.可以借助rank數(shù)組直接比較字典序.只是要注意在考察點kL時,要把以(k-1)L+1,...,(k+1)L-1為起點的子串都訪問一遍找最小rank者.

            pku1743(中) 后綴數(shù)組
            找一個串的最長不重疊相同子串.
            由于某子串可能整體加上(或減去)相同偏移量,因此不直接對原串操作,而是構(gòu)造新串b, 其中b[i]=a[i]-a[i-1]. 此時求得最長不重疊相同子串的長度+1便是結(jié)果.
            可以二分長度,或者棧掃描(*)直接求最大長度.

            whu1084(易) 后綴數(shù)組
            求重復(fù)次數(shù)最多的不重疊子串長度
            spoj687的簡單版,不要求循環(huán)節(jié)連續(xù),直接二分長度即可.

            pku2778(易) 多串匹配+DP AC自動機(jī),trie圖
            字符集大小為4, 給出m個(m<=10)禁止單詞(長度<=10), 求長度為n(n<=2*10^9)的不包含任何禁止單詞的串的個數(shù).
            對禁止單詞建立trie圖,并計算出圖中任意合法結(jié)點之間的轉(zhuǎn)移數(shù),這樣便求得1步轉(zhuǎn)移矩陣.
            做n次方后的矩陣,第1行中屬于合法狀態(tài)的元素之和即為解.
            禁止單詞總長度不超過100,因此合法狀態(tài)亦<100.總復(fù)雜度100^3*logN

            zju3228(中) Searching the String 后綴數(shù)組,AC自動機(jī),trie圖
            原串長10^5, 現(xiàn)在有10^5次查詢, 每次查詢一個長度<=6的模式串在原串中的最大匹配次數(shù).
            模式串的匹配方式有可重疊和不可重疊兩種, 需針對查詢的類型返回相應(yīng)值.
            后綴數(shù)組解法(在線):
            對原串建立sa和height數(shù)組.由于模式串長度最大只有6, 我們可以將height數(shù)組分別按L=1..6分組,預(yù)處理求出相應(yīng)長度每組內(nèi)不重疊子串的最大匹配次數(shù),此過程O(6*nlogn).
            另外由于sa數(shù)組將所有后綴按字典序排好了,所以對一個詢問, 可以二分找到它在sa中第一次出現(xiàn)的位置p1和最后一次出現(xiàn)的位置p2, 則p2-p1+1就是可重疊匹配的答案. 對不可重疊匹配,只需直接返回p1處預(yù)處理時的值. 每次查詢O(logn).
            trie圖,AC自動機(jī)解法(離線):
            把所有查詢建trie圖, 對圖中的每個有效結(jié)點維護(hù):該串長度,兩類查詢的計數(shù),該串上一次被匹配的位置, 還要用個鏈表記下這個串屬于哪些查詢.
            剩下的就是經(jīng)典的自動機(jī)多串匹配了.


            (*)關(guān)于棧掃:
            height數(shù)組具有區(qū)間性,各個不同前綴被相應(yīng)的極小值隔開,而一個區(qū)間中又有多個子區(qū)間.各區(qū)間值大于區(qū)間端點的部分互不影響.因此可以維護(hù)一個存放height值不減的棧,棧中每個元素的附屬值, 記錄了它在棧中相鄰的兩個元素為端點的連續(xù)區(qū)間內(nèi)所有height值不小于它的必要信息.比如此題要記錄height>=k的連續(xù)區(qū)間內(nèi)sa[i] 的最大值和最小值.
            棧掃描的經(jīng)典例子移步pku2559.


            (**)trie圖備忘:
            比trie樹多了個后綴指針psuf. 設(shè)當(dāng)前結(jié)點字母為c, 則psuf指向父親的后綴的pch[c].
            trie樹中的后代結(jié)點指針pch(已經(jīng)更名為狀態(tài)轉(zhuǎn)移指針),當(dāng)相應(yīng)后代存在時,指向后代;否則指向當(dāng)前結(jié)點的后綴的相應(yīng)后代,即pch[k]=node[pa].pch[k].
            后綴指針: 在接下來的狀態(tài)轉(zhuǎn)移中,當(dāng)前結(jié)點與它的后綴結(jié)點等價.
            后代結(jié)點指針: 在當(dāng)前狀態(tài)下,接收到字符ch時,轉(zhuǎn)移到pch[ch]指向的結(jié)點.
            posted on 2009-07-16 19:10 wolf5x 閱讀(1539) 評論(2)  編輯 收藏 引用 所屬分類: acm_icpc

            FeedBack:
            # re: 字符串匹配 后綴數(shù)組 trie圖(更新)
            2009-09-23 15:19 | 小狗
            O(n*(n/1+n/2+...+n/n)) = O(nlogn)

            這里有錯~~  回復(fù)  更多評論
              
            # re: 字符串匹配 后綴數(shù)組 trie圖(更新)
            2009-10-08 17:17 | <A href="mailto:wolf5x1016@gmail.com"
            @小狗
            Thanks~~ 手誤了  回復(fù)  更多評論
              
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            "Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

            留言簿(3)

            隨筆分類(59)

            隨筆檔案(43)

            cows

            搜索

            •  

            最新評論

            評論排行榜

            亚洲AV无码一区东京热久久| 久久久精品日本一区二区三区| 大香伊人久久精品一区二区| 亚洲精品午夜国产VA久久成人| 成人国内精品久久久久影院| 久久精品无码免费不卡| 久久久这里只有精品加勒比 | 99久久精品日本一区二区免费 | 久久久久久久97| 久久福利青草精品资源站免费| 久久精品无码一区二区三区日韩 | 伊人久久大香线蕉综合影院首页| 亚洲乱亚洲乱淫久久| 久久狠狠爱亚洲综合影院 | 97精品国产97久久久久久免费 | 久久福利青草精品资源站| 欧美黑人激情性久久| 国产亚州精品女人久久久久久| 精品久久亚洲中文无码| 国产免费久久精品丫丫| 国产成人久久激情91| 一本色道久久综合亚洲精品| 久久成人18免费网站| 69久久夜色精品国产69| 一本色道久久99一综合| 久久精品无码av| 久久久久久国产精品免费免费| 国内精品人妻无码久久久影院| 久久国产劲爆AV内射—百度| 亚洲精品成人网久久久久久| 久久99热这里只有精品国产| 久久se精品一区二区| 欧美久久综合性欧美| 久久久无码一区二区三区| 色欲av伊人久久大香线蕉影院| 亚洲人AV永久一区二区三区久久| 久久精品国产精品亚洲人人| 久久伊人五月天论坛| 伊人久久大香线蕉成人| 中文字幕久久久久人妻| 亚洲精品蜜桃久久久久久|