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
          主站蜘蛛池模板: 巴楚县| 长春市| 北辰区| 杨浦区| 宁安市| 花莲县| 获嘉县| 隆德县| 云和县| 永安市| 万宁市| 年辖:市辖区| 景德镇市| 江阴市| 安泽县| 青铜峡市| 乌兰县| 红河县| 巧家县| 阳东县| 宁国市| 山阳县| 九江县| 怀仁县| 韶关市| 易门县| 南充市| 汾阳市| 界首市| 城步| 额济纳旗| 普宁市| 威宁| 闽侯县| 苍溪县| 榆中县| 沙湾县| 共和县| 西乌| 靖远县| 广安市|