• <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 閱讀(12252) 評論(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无一区二区三区久久 | 午夜人妻久久久久久久久| 狠狠久久综合伊人不卡| 国产巨作麻豆欧美亚洲综合久久| 国产精品美女久久久久网| 好久久免费视频高清| 久久精品国产亚洲AV高清热| 无码国内精品久久人妻蜜桃| 嫩草伊人久久精品少妇AV| 久久亚洲AV成人无码电影| 久久亚洲欧美国产精品| 精品久久久久久久| 93精91精品国产综合久久香蕉| 亚洲乱亚洲乱淫久久| 久久久久久A亚洲欧洲AV冫| 午夜精品久久久久久| 欧美精品乱码99久久蜜桃| 亚洲精品国产美女久久久| 久久夜色精品国产噜噜噜亚洲AV | 久久成人国产精品免费软件| 伊人久久大香线蕉精品不卡| 亚洲精品乱码久久久久久| 久久99精品久久久久婷婷| 国产高潮久久免费观看| 久久人人爽人人爽人人片AV东京热| 久久亚洲AV无码精品色午夜麻豆| 人妻精品久久无码区| 亚洲国产精品久久久久| 欧美亚洲国产精品久久| 国产精品久久久久久| 久久久久亚洲爆乳少妇无| 亚洲精品白浆高清久久久久久| 亚洲国产精品久久66| 97精品依人久久久大香线蕉97 | 精品久久久久久国产| 久久综合视频网站| 无码精品久久久久久人妻中字| 国内精品伊人久久久久网站| 久久免费的精品国产V∧|