• <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 | 程序員面試之家
            国产精品久久久香蕉| 99久久精品国产毛片| 久久99国产综合精品女同| 成人久久精品一区二区三区| 色综合久久天天综合| 午夜精品久久久久久影视riav| 一本色道久久99一综合| 国内精品久久久久久久涩爱 | 国产麻豆精品久久一二三| 久久精品国产精品亚洲艾草网美妙| 亚洲AV乱码久久精品蜜桃| 伊人丁香狠狠色综合久久| 亚洲香蕉网久久综合影视| 久久精品国产亚洲一区二区三区| 午夜精品久久久久久久久| 亚洲欧美成人久久综合中文网| 久久国产精品久久| 99久久精品毛片免费播放| 狠狠色婷婷久久一区二区| 欧美亚洲日本久久精品| 情人伊人久久综合亚洲| 国产精品久久久久久久久鸭| 精品国产99久久久久久麻豆| 午夜精品久久久久9999高清| 伊人久久大香线蕉精品| 国产成人AV综合久久| 国产99久久九九精品无码| 久久久久久久尹人综合网亚洲| 精品久久久久久中文字幕人妻最新| 久久人人爽人人爽人人片AV东京热| 久久伊人中文无码| 久久天天躁狠狠躁夜夜av浪潮| 久久久99精品成人片中文字幕 | 久久九九免费高清视频| 国内精品久久久久影院网站| 99久久精品无码一区二区毛片 | 狼狼综合久久久久综合网| 精品国产乱码久久久久软件| 久久精品中文无码资源站| 久久久久久免费视频| 久久精品欧美日韩精品|