編程算法 - 後綴樹(Suffix Tree) 代碼(C)

後綴樹(Suffix Tree) 代碼(C) 

給你一個長字符串s與很多短字符串集合{T1,, T2, ...}, 設計一個方法在s中查詢T1, T2, ..., 要求找出Ti在s中的位置.

代碼:

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

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class SuffixTreeNode {
 map<char, SuffixTreeNode*> children;
 char value;
 vector<int> 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<int> 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<int> empty;
    return empty;
   }
  }
 }

 ~SuffixTreeNode() {
  map<char, SuffixTreeNode*>::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<s.length(); ++i) {
   string suffix = s.substr(i);
   root->insertString(suffix,i);
  }
 }
 vector<int> 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<int> li = tree.getIndexes(stringList[i]);
  if (li.size() != 0) {
   cout << stringList[i] << "  ";
   for (int j=0; j<li.size(); ++j)
    cout << li[j] << " ";
   cout << endl;
  }
 }

 return 0;
}

輸出:

is  1 4
sip  6
sis  3