• <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>
            隨筆 - 6, 文章 - 0, 評論 - 24, 引用 - 0
            數據加載中……

            Suffix Tree—后綴樹

            Suffix tree—后綴樹

            l  簡介

            后綴樹是一種PAT樹,它描述了給定字符串的所有后綴,許多重要的字符串操作都能夠在后綴樹上快速地實現。

            l  定義

            一個長度為n的字符串S,它的后綴樹定義為一棵滿足如下條件的樹:

            n  從根到樹葉的路徑與S的后綴一一對應。即每條路徑惟一代表了S的一個后綴;

            n  每條邊都代表一個非空的字符串;

            n  所有內部節點(根節點除外)都有至少兩個子節點。

            由于并非所有的字符串都存在這樣的樹,因此S通常使用一個終止符號進行填充(通常使用$)。

            l  優點

            n  匹配快。對于長度為m的模式串,只需花費至多O(m)的時間進行匹配。

            n  空間省。Suffix tree的空間耗費要低于Suffix trie,因為Suffix tree除根節點外不允許其內部節點只含單個子節點,因此它是Suffix trie的壓縮表示。





            待續……

            posted on 2009-03-29 13:05 yuyang7 閱讀(12274) 評論(8)  編輯 收藏 引用 所屬分類: 數據結構

            評論

            # re: Suffix Tree—后綴樹  回復  更多評論   

            學習~~
            簡介中第一句“所有前綴”是不是應該是“所有后綴”?
            另外,請教博主,你的圖畫得很漂亮,不知道是用什么工具畫的?
            2009-03-29 14:11 | t

            # re: Suffix Tree—后綴樹  回復  更多評論   

            @t
            筆誤,已更正。
            圖其實是用PowerPoint畫的。
            2009-03-29 14:22 | yuyang7

            # re: Suffix Tree—后綴樹  回復  更多評論   

            @yuyang7
            PowerPoint?強!
            2009-03-29 16:55 | t

            # re: Suffix Tree—后綴樹[未登錄]  回復  更多評論   

            應該再詳細些阿 。。。。
            2009-06-22 21:43 | Simon

            # re: Suffix Tree—后綴樹  回復  更多評論   

            不錯,說得很清楚。
            2010-08-08 21:36 | 游客

            # re: Suffix Tree—后綴樹  回復  更多評論   

            準備實做下
            2011-01-28 23:42 | 神奇哥

            # re: Suffix Tree—后綴樹  回復  更多評論   

            不錯,頂下
            2011-05-24 16:01 |

            # re: Suffix Tree—后綴樹  回復  更多評論   

            8錯
            2011-09-22 09:51 | 程序員面試之家
            亚洲AV无码1区2区久久| 久久精品中文字幕一区| 亚洲精品乱码久久久久久蜜桃图片| 久久综合伊人77777| 国产精品一区二区久久精品涩爱 | 久久人人爽人爽人人爽av| 伊人色综合九久久天天蜜桃| 亚洲AV成人无码久久精品老人| 狠狠色丁香久久综合五月| 无夜精品久久久久久| 91精品国产综合久久婷婷| 亚洲色欲久久久久综合网| 国产∨亚洲V天堂无码久久久| 亚洲国产视频久久| 99久久婷婷国产一区二区| 亚洲AV无码久久寂寞少妇| 四虎亚洲国产成人久久精品| 69久久精品无码一区二区| 久久国产AVJUST麻豆| 久久天天躁狠狠躁夜夜不卡| 国产产无码乱码精品久久鸭| 久久这里都是精品| 青青草原综合久久大伊人导航| 久久青青草原综合伊人| 人妻丰满AV无码久久不卡| 国产精品久久久久久久久久影院| 九九久久精品无码专区| 色综合久久88色综合天天 | 精品久久久久久无码人妻热| 国产精品久久成人影院| 久久综合给合久久国产免费| 一本一本久久a久久综合精品蜜桃| 久久精品无码专区免费| 国产毛片久久久久久国产毛片| 久久综合中文字幕| 国产精品视频久久久| 色综合久久无码五十路人妻| 无码国内精品久久人妻| 狠狠色丁香婷婷久久综合不卡| 热久久这里只有精品| 久久www免费人成精品香蕉|