程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 編程算法 - 後綴樹(Suffix Tree) 代碼(C)

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

編輯：關於C語言

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

後綴樹(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; iinsertString(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