编程算法 - 后缀树(Suffix Tree) 代码(C) - c语言编程

TOP

编程算法 - 后缀树(Suffix Tree) 代码(C)

2015-01-22 20:50:04 来源: 作者: 【大中小】浏览:15次

后缀树(Suffix Tree) 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

给你一个长字符串s与很多短字符串集合{T1,, T2, ...}, 设计一个方法在s中查询T1, T2, ..., 要求找出Ti在s中的位置.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.20
 *      Author: Spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include 
  
   
#include 
   
     #include 
     using namespace std; class SuffixTreeNode { map
     
       children; char value; vector
      
        indexes; public: SuffixTreeNode() {} void insertString(string s, int index) { indexes.push_back(index); if (s.length() > 0) { value = s[0]; SuffixTreeNode* child = NULL; if (children.find(value) != children.end()) { child = children[value]; } else { child = new SuffixTreeNode(); children[value] = child; } string remainder = s.substr(1); child->insertString(remainder, index); } } vector
       
         getIndexes(string s) { if (s.length() == 0) return indexes; else { char first = s[0]; if (children.find(first) != children.end()) { string remainder = s.substr(1); return children[first]->getIndexes(remainder); } else { vector
        
          empty; return empty; } } } ~SuffixTreeNode() { map
         
          ::iterator it; for (it!=children.begin(); it!=children.end(); ++it) delete it->second; } }; class SuffixTree { SuffixTreeNode* root; public: SuffixTree(string s) { root = new SuffixTreeNode; for (int i=0; i
          
           insertString(suffix,i); } } vector
           
             getIndexes(string s) { return root->getIndexes(s); } ~SuffixTree() {} }; int main(void) { string testString = "mississippi"; string stringList[] = {"is", "sip", "hi", "sis"}; SuffixTree tree (testString); for (int i=0; i<4; i++) { vector
            
              li = tree.getIndexes(stringList[i]); if (li.size() != 0) { cout << stringList[i] << " "; for (int j=0; j
             
              

              输出:
              
              
              is  1 4 
sip  6 
sis  3


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C语言格式化输出函数及使用禁区	下一篇：数据结构（C实现）------- 串

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: