posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          后綴樹的在線生成算法

          Posted on 2007-11-07 21:08 ZelluX 閱讀(1875) 評論(1)  編輯  收藏 所屬分類: Algorithm
          第一次接觸后綴樹應(yīng)該是在某次省隊集訓(xùn),徐串大牛做的講座。
          不過當(dāng)時只是有了個印象。
          現(xiàn)在發(fā)現(xiàn)這東東還是很好用的  @,@

          http://www.aygfsteel.com/Files/zellux/SuffixT1withFigs.rar

          On–line construction of suffix trees
          by Esko Ukkonen

          Key Words.
          Linear time algorithm, suffix tree, suffix trie, suffix automaton, DAWG.

          Abstract.
          An on–line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It has always the suffix tree for the scanned part of the string ready. The method is developed as a linear–time version of a very simple algorithm for (quadratic size) suffix tries. Regardless of its quadratic worst-case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give in a natural way the well–known algorithms for constructing suffix automata (DAWGs).


          評論

          # re: 后綴樹的在線生成算法  回復(fù)  更多評論   

          2008-03-18 03:21 by ss
          100101
          主站蜘蛛池模板: 道真| 深水埗区| 枣庄市| 梧州市| 平和县| 吴桥县| 郎溪县| 察隅县| 同心县| 延津县| 红河县| 台湾省| 方山县| 平山县| 抚顺县| 辽宁省| 原平市| 尉犁县| 海丰县| 江孜县| 江北区| 自贡市| 文山县| 邵武市| 常熟市| 昌都县| 竹溪县| 黄骅市| 永丰县| 咸阳市| 鄂尔多斯市| 邻水| 达孜县| 武邑县| 桐乡市| 南召县| 夏津县| 江口县| 绥江县| 大渡口区| 瓦房店市|