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

          后綴樹的在線生成算法

          Posted on 2007-11-07 21:08 ZelluX 閱讀(1876) 評論(1)  編輯  收藏 所屬分類: Algorithm
          第一次接觸后綴樹應(yīng)該是在某次省隊(duì)集訓(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
          主站蜘蛛池模板: 温宿县| 林州市| 获嘉县| 鄂伦春自治旗| 蒙山县| 和龙市| 分宜县| 临猗县| 化州市| 桂阳县| 河间市| 邵阳市| 黎城县| 贵州省| 楚雄市| 独山县| 察雅县| 门头沟区| 象山县| 弥勒县| 香港| 丘北县| 平塘县| 自治县| 莱州市| 富裕县| 肇州县| 泸州市| 安图县| 龙里县| 普陀区| 隆回县| 佛教| 漳平市| 长顺县| 龙泉市| 延长县| 平谷区| 隆化县| 霍林郭勒市| 黔西|