suffixtree.h

后缀树的Ukkon算法实现

#ifndef __SUFFIXTREE_H
#define __SUFFIXTREE_H

//#define DEBUG


//对于叶节点,通过m_nActiveLen和m_nEdgeLabelEndPos可以得到节点对应的字符串.对于分支节点,也是如此.
struct tagSuffixNode
{
public:
    tagSuffixNode* m_tpChild; //子节点,如果为0,说明是叶子节点
    //tagSuffixNode* m_tpParent; //父节点,根节点的父节点为0
    tagSuffixNode* m_tpLeftSibling; //左兄弟
    tagSuffixNode* m_tpRightSibling; //右兄弟
    tagSuffixNode* m_tpMostRightChild;//最右子节点
    tagSuffixNode* m_tpSuffixLink; //指向当前节点表示的子串的最大后缀所对应的分支节点

    int m_nActiveLen; //节点代表的字符串的长度.    
    int m_nEdgeLabelStartPos; //入边开始字符的下标.对于分支节点,只是用来表示边对应的字符串是什么,并不表示其在子孙叶节点表示的串中对应位置的字符在整个串中的下标.
    int m_nEdgeLabelEndPos; //入边结束字符的下标
    bool m_bIsLeaf; //是否是叶节点

    //char m_cIndex; //test


public:
    void init()
        {
            m_tpChild = 0;
           // m_tpParent = 0;
           m_tpLeftSibling = 0;
            m_tpRightSibling = 0;
            m_tpMostRightChild = 0;
            m_tpSuffixLink = 0;

            m_nEdgeLabelStartPos = 0;
            m_nEdgeLabelEndPos = 0;

            m_nActiveLen = 0;
            m_bIsLeaf = true;
        }
};

class SuffixTree{

public:
	SuffixTree(char*);
	void constuct();
	int search(char*);						//查询字符串，若找到返回首位置
	int numberOfSubchar(char *);	//查找指定字符串在树中出现的次数
	int findNumberOfLeaf( tagSuffixNode* );
	tagSuffixNode* getRoot();




private:

	int m_nStrLen;					//字符串长度(包括后加#)			
	char *m_cpInternalStr;		//字符串的内部存储
	tagSuffixNode* top;			//最上层节点
	tagSuffixNode* root;		//根节点

	// (globalS,(globalK,i-1)) the canonical reference pair of active point
	tagSuffixNode *globalS;					
	int globalK;	

	bool endPoint;					//是否找到结束结点
	int labelOfEnd;					//每次添加字符过程中，最后一个字符的标记，叶子结点


	tagSuffixNode* __allocNode();						//分配一个新的结点

	void update(int);													//内部函数，见Ukkonen算法的实现
	tagSuffixNode* testAndSplit(int,char);			//内部函数，见Ukkonen算法的实现
	tagSuffixNode* __findTTransition(tagSuffixNode* , char );  //查找结点node的以char字符开始的边
	void canonize(tagSuffixNode* , int);				//内部函数，见Ukkonen算法的实现
	



};


#endif //