• <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无一区二区三区久久| 久久综合给合久久狠狠狠97色69 | 欧美777精品久久久久网| 四虎国产精品成人免费久久| 精品国产VA久久久久久久冰 | 狠狠狠色丁香婷婷综合久久五月| 久久精品免费大片国产大片| 日韩人妻无码一区二区三区久久| 91久久精品国产成人久久| 久久精品国产乱子伦| 久久久WWW成人| 久久精品一区二区三区不卡| 久久久久久久久久久精品尤物| 一本久久久久久久| 国产亚洲精品自在久久| 精品国产青草久久久久福利| 国产69精品久久久久99| 99热成人精品免费久久| 91精品国产综合久久婷婷| 亚洲综合伊人久久综合| 久久伊人精品一区二区三区| 亚洲国产精品一区二区三区久久 | 亚洲综合精品香蕉久久网97| 99久久99久久| 国产精品美女久久久久久2018| 伊人久久久AV老熟妇色| 亚洲va中文字幕无码久久不卡| 久久人人爽人人澡人人高潮AV | 中文字幕久久精品| 久久精品国产99久久久古代 | 久久久久中文字幕| 91久久精品91久久性色| 97精品久久天干天天天按摩 | 青春久久| 国产69精品久久久久观看软件| 久久久久精品国产亚洲AV无码| 一本大道久久香蕉成人网| 久久久久久免费视频| 久久亚洲春色中文字幕久久久|