main.cpp

后缀树构造软件

#include"afx.h"
#include<stdio.h>

#include<string>
#include<iostream>
//#include<stack>
#include<queue>
using namespace std;

#include<vector>
using std::string;


struct node {
		string word;
		node* point_child ;
		node* point_brother ;

		vector<int> wenzhang;
	
		
	};// 定义结点



	  int compare(string a,string b){
		int len,i;
		if(a.length() >= b.length())len=b.length();	
		else len=a.length();

		for( i=0;i<len;i++){
			if(a.substr(i,1)!=b.substr(i,1)){
				
				
				return i;
			}
		}
		return i;
	};



void main() {


    queue<node*> stk;//定义一个存放结点指针的队列；
	string s,sub,compare_string,stk_string;
	


	node root;
	root.word = "";//根节点
	root.point_brother = NULL;


	  
    node* stack_in_point,*stack_out_point,*select_point;

	node child;
	//child.word = s;
	root.point_child = &child;
	child.point_brother = NULL;
	child.point_child = NULL;



	child.wenzhang.push_back(1);

    select_point = &root;

/*	{	wenzhang* p =new wenzhang;
	p->wenzhangbianhao = 1;
	p->zifuchuanweizhi = 0;
	child.point_child = p;
	}

*/
    stk.push(select_point->point_child);

int times;
int i;
	cin>>times;
	for (int z =0 ;z<times;z++){
		cin>>s;
		cout<<endl;



		if(times>=2 && z>=1)
		{
			i =0;
			compare_string = s;


		}//不是第一个字符串
		else 
		{
			i=1;
			child.word = s;
		}//第一个字符串


		
for(;i<s.length();i++){

    stack_in_point = select_point->point_child;
	                                                        
	compare_string = s.substr(i,(s.length()-i));//原始字符串


        /* cout<<sub<<endl;//输出从i＝0开始的各个子字符串*/
		while(stack_in_point != NULL){
        stk.push(stack_in_point);
		
		stack_in_point = stack_in_point->point_brother;
		}//    把所有兄弟进栈 


	while(!stk.empty()){


		stack_out_point = stk.front();
		stk.pop();//出栈

		stk_string = stack_out_point->word;

         int r;
		r=::compare(compare_string,stk_string);//返回子字符串与母字符串不同的字符的位置

		if(r!=0 && r == stk_string.length() && r == compare_string.length()) {

			stack_out_point->wenzhang.push_back(z+1);

			while(!stk.empty())stk.pop();
			break;
		
						
		}

		if(r==0 ){                      //完全不一样

			if(stk.empty()) {
				node* u = new node;
				u->word = compare_string;
				stack_out_point->point_brother = u;

				u->wenzhang.push_back(z+1);

				                                           
				u->point_brother = NULL;
				u->point_child = NULL;
				while(!stk.empty())stk.pop();

			}


		}//////////////////////////////////////////////////////////////////////////////////////
		if(r!=0&&r==stk_string.length() ){
			if (stack_out_point->point_child != NULL ){           //

			   compare_string = compare_string.substr(r,compare_string.length()-r);              //
stack_out_point->wenzhang.push_back(z+1);
               while(!stk.empty())stk.pop();
			   stack_in_point = stack_out_point->point_child;
			   while(stack_in_point != NULL){
                            stk.push(stack_in_point);
		
		                    stack_in_point = stack_in_point->point_brother;
			   }//    把所有兄弟进栈 
			   continue;
			}
			else 
			{
				node* u = new node;
				u->word = compare_string.substr(r,compare_string.length()-r);
				stack_out_point->point_child = u;


				u->wenzhang.push_back(z+1);

				u->point_brother = NULL;
				u->point_child = NULL;

				stack_out_point->wenzhang.push_back(z+1);
			    while(!stk.empty())stk.pop();
			}


		}/////////////////////////////////////////////////////////////////////////////////////////
        
		if(r!=0 && r == compare_string.length() ){
			if(stack_out_point->point_child == NULL){//叶子结点


					node* v =new node;
			v->word = stk_string.substr(r,stk_string.length() - r );
			stack_out_point->point_child = v;
			stack_out_point->word = compare_string;

			v->wenzhang = stack_out_point->wenzhang;
			//stack_out_point->wenzhang.clear();
			stack_out_point->wenzhang.push_back(z+1);


			v->point_brother = NULL;
			v->point_child = NULL;
			}

			else {                                   //不是叶子结点
				node* o = new node;
				o->word = stk_string.substr (r,stk_string.length() - r );
				o->point_child = stack_out_point->point_child;

				o->wenzhang = stack_out_point->wenzhang;
				//stack_out_point->wenzhang.clear();
				stack_out_point->wenzhang.push_back(z+1);


				stack_out_point->point_child = o;
				stack_out_point->word = compare_string;
				o->point_brother = NULL;
			}
				while(!stk.empty())stk.pop();
		}




		if(r!=0 && r!= compare_string.length() && r !=stk_string.length () ){                    //找到部分匹配
             
					if(stack_out_point->point_child == NULL){//插入结点处为叶子结点


			node* n_1,* n_2;

			n_1 = new node;
			n_1->word = stk_string.substr(r,stk_string.length()-r);
			stack_out_point->point_child = n_1;
			n_1->wenzhang = stack_out_point->wenzhang ;
			
			n_2 = new node;
			n_2->word = compare_string.substr(r,compare_string.length()-r);
			n_1->point_brother = n_2;
			n_2->wenzhang.push_back(z+1);


			n_1->point_child = NULL;
			n_2->point_brother = NULL;
			n_2->point_child = NULL;

			stack_out_point->word = stk_string.substr(0,r);
			//stack_out_point->wenzhang.clear();
			stack_out_point->wenzhang.push_back(z+1);
			
					}


					else {//插入结点为非叶子结点


									node* n_1,* n_2;

			n_1 = new node;
			n_1->word = stk_string.substr(r,stk_string.length()-r);
			n_1->point_child = stack_out_point->point_child;

			n_1->wenzhang = stack_out_point->wenzhang;


			stack_out_point->point_child = n_1;

			n_2 = new node;
			n_2->word = compare_string.substr(r,compare_string.length()-r);
			n_1->point_brother = n_2;

			n_2->wenzhang.push_back(z+1);

		
			n_2->point_brother = NULL;
			n_2->point_child = NULL;

			stack_out_point->word = stk_string.substr(0,r);
stack_out_point->wenzhang.push_back(z+1);
			//stack_out_point->wenzhang.clear();
			
					}
							while(!stk.empty())stk.pop();

					
		}
	
	}


}
node* q = select_point->point_child;
while(q !=NULL){
	stk.push(q);
	
	q=q->point_brother;
}

while(!stk.empty()){
	stack_out_point = stk.front();
	stk.pop();
	if(stack_out_point->point_child !=NULL)q = stack_out_point->point_child;

	if(stack_out_point->point_brother==NULL ){
		cout<<stack_out_point->word;
		int cursor=stack_out_point->wenzhang.size();
		for(int w=0;w<cursor;w++) {
			cout<<stack_out_point->wenzhang[w];
		}
		cout<<endl;
		}
		
	else {		cout<<stack_out_point->word;
		int cursor=stack_out_point->wenzhang.size();
		for(int w=0;w<cursor;w++) {
			cout<<stack_out_point->wenzhang[w];
		}
		cout<<" ";


		}
	

	while(q!=NULL){
		stk.push(q);
		q=q->point_brother;
	}

}

}
}