SuffixTree

早上照着书本敲了一个小时
崩掉了，先扔这里，以后再调试

#include<cstdio>
#include<cstring> 
#include<vector>
#include<list>
using namespace std;
//后缀树节点预备备 
struct SfxNode{
	char *l,*r;//指向字符数组的指针，表示其父亲边标记为子串[l,r)
	SfxNode* SfxLink; //好名字，后缀链，指向第一个节点
	list<int> from;//推广到多串的形式
	SfxNode* father;//在后缀树中的父亲节点
	SfxNode* firstCh;//在后缀树中的第一个孩子节点（如果没有，那么为叶节点）//说实话忘记了这是用来干什么的
	SfxNode* left;//左兄弟,即父亲的孩子排列中排在该节点前一个的节点//似乎是为了应用扩展规则
	SfxNode* right;//右兄弟，与上面类似
	//获取当前节点的孩子中，边标记以c开始的那个孩子//与技巧一配合
	SfxNode* child(char c)const{
	SfxNode *p=NULL;
	if (firstCh&&*firstCh->l<=c)
	 p=firstCh;    //这一步不是很理解，为什么要小于等于c，不是直接找标记以c开始的那个孩子吗？ 
	 else return p;//不存在，直接返回空指针 
	 while (p->right&&*p->right->l<=c)
	  p=p->right;//找到编号小于等于c的最大的孩子（如果有编号为c就返回该孩子，否则返回将要插入位置的左兄弟） 
	  return p; 
	} 
	
	//添加新的子节点add。p为add的左兄弟
	void addChild(SfxNode* p,SfxNode* add){
		if (p)
		{
		   add->right=p->right;
		   add->left=p;
		   p->right=add;
		   if (add->right)  
		     add->right->left=add;//一系列链表维护的基本操作，简单 
		}
		else {
			//否则为第一个孩子节点
			add->left=NULL;
			add->right=firstCh;
			firstCh=add;
			if (add->right) 
			  add->right->left=add;
		}
		add->father=this;//更新父亲节点 
	} 
}; 

SfxNode sfxNodePool[400000+100];//后缀节点的手工内存池（考虑到效率和安全）
int SfxNodeCnt=0;//当前树中节点个数
 
//后缀树开搞 
struct SuffixTree{
	SfxNode* root;//根节点
	SuffixTree():root(newNode()),texts(),textLens()
	{}~SuffixTree(){clear();}//构造和析构函数
	//将text所有后缀加入到后缀树中（字符数组'\0'结尾，所以正好将其为终止符$）
	void addText(const char* text)
	{
	   //一些初始化操作，变量定义见该类的private部分
	    cutTextt=cutPos=text;lastAddPos=0;activeNode=root;
		root->l=root->r=curText;
		cutTextLen=strlen(text);
		for (int i=0;i<cutTextLen;i++)
		{
			newlyAddNode=NULL;
			//每个阶段的扩展。依据单调性从上次最后扩展的位置开始
			for (int j=lastAddPos;j<=i;j++)
			  //如果扩展不成功，（即满足扩展规则3，那么终止本阶段之后的所有扩展）
			  if (!extend(curText+j,curText+i)) break; 
		 } 
		 //将插入的字符串备份
		 
		 texts.push_back(curText);textLens.push_back(curTextLen);  
	   	
	}
	
	void clear()
	{
	SfxNodeCnt=0;root=newNode();
	texts.clear();textLens.clear();
	 } 
	 //为了遍历后缀树的临时数组
	 char str[10000];
	 
	 //遍历后缀树，供测试用
	 void travel(SfxNode* curNode,int curindex)
	 {
	 	for (const char*i=curNode->l;i!=curNode->r;++i)
	 	{
	 		str[curindex++]==*i;
	 		if (curNode->firstCh)
	 		{
	 			for (SfxNode* node=curNode->firstCh;node;node=node->right)
                   travel(node,curindex);
			 }else printf("%s\n",str);
		 }
	  } 
	private:
		//用来备份插入的字符串 
		vector<const>texts;vector<list> textLens;
		SfxNode * activeNode,*newlyAddNode;//当前被激活的节点和新添加的节点
	     //每次添加的时候从被激活的节点开始向下走；记录新添加的节点的原因是为了维护它的后缀链
		 const char* curPos;//当前扩展的位置
		 const *curText;//插入的字符数组的指针
		 int lastAddPos;//上阶段最后的扩展位置，利用其单调性保证算法线性
		 int curTextLen;//插入到后缀树中的字符串的长度
	    //新建一个节点，手工实现内存管理
		SfxNode* newNode(const char* l=NULL,const char* r=NULL)
		{
			SfxNode* p=&SfxNodePool[sfxNodeCnt++];
			p->l=l;p->r=r;//设置新建节点的父亲边的标记
			p->from.clear();
			p->SfxLink=p->faher=p->firstCh=p->left=p->right=NULL;
		   return p;	 
		}
		//从被激活的节点开始向下走直到找到要找的字符串[l,r）
		void goDown(const char* l,const char * r)
		{
			curPos=activeNode->r;
			while (l<r)
			{
				activeNode=activeNode->child(*l);
				if (r-l<=activeNode->r-activeNode->l)//如果要找的位置就在该边内
				{
					
					curPos=activeNode->l+(r-l);
					return;
				} 
				else {
					curPos=activeNode->r;
					l+=activeNode->r-activeNode->l;
				}
			}
		}
		//扩展，将子串[l,r)插入到隐式树中，返回是否插入成功（即是不满足扩展规则3）
		bool extend(const char* i,const char * r)
		{
			if (curPos<activeNode->r)
			{
				const char * l;
				if (*curPos==*r)
				{
					 if(*r) //如果不是最后一次扩展，那么当前就扩展完了 
                     {
                     	curPos++;
                     	return false;
					 }
					 activeNode->from.push_back(texts.size());//记录位置
					 l=r-(avtiveNode->r-activeNode->l-1); 
				}
				else {
					SfxNode* in=newNode(active->l,curPos);//新建中间节点
					in->left=activeNode->left;
					in->right=activeNode->right;
					in->father=activeNode->father;
					if (activeNode->left)
					   activeNode->left->right=in;
					if (activeNode->right)
					   activeNode->right->left=in;
					if (activeNode->father->firstCh==activeNode)
					   activeNode->father->firstCh=in;
					in->addChild(NULL,activeNode);//以上操作维护树边及兄弟指针
					activeNode->l=curPos;//应用扩展规则2，新建叶节点
					SfxNode *leaf=newNode(r,curText+curTextLen+1);
					in->addChild(in->child(*r),leaf);
					lastAddPos++;
					leaf->from.push_back(texts.size());
					//维护后缀链
					if (newlyAddNode) newlyAddNode->SfxLink=in;
					activeNode=newlyAddNode=in;
					l=r-(activeNode->r-active->l); 
				}
				activeNode=activeNode->father;
				if (activeNode->SfxLink)
				  activeNode=activeNode->SfxLink;
				else l++;
				goDown(l,r);//向下走找到下次扩展的位置，即更新激活节点
				 
			}
			else {
				//终止在节点处而不是在边内部 
				if (newlyAddNode)
				{
					newlyAddNode->SfxLink=activeNode;
					newlyAddNode=NULL;
				}
			   SfxNode * ch=activeNode->child(*r);
			   if (ch&&(ch->l==*r))
			   {
			   	if (*r)
			   	
			   	   {
			   	   	activeNode=ch;
			   	   	curPos=activeNode->l+1;
					return false; 
					  }
			     ch->from.push_back(texts.size());
			   }
			else {
				SfxNode * leaf=newNode(r,curText+curTextLen+1);
				activeNode->addChild(ch,leaf);
				lastAddPos++;
				leaf->from.push_back(texts.size());
			}
			if (i<r)
			  {
			  	activeNode=activeNode->SfxLink;
			  	curPos=activeNode->r;
			  }
			     
			}
			return true;
			 
			  }	  
};

SuffixTree tree;
int main()
{
	tree.addText("xabxac");
	tree.travel(tree.root,0);
	return 0;
}