suffixtree1.cpp

这是一个实现SuffixTree的程序源代码。 是我个人编的。 希望大家参考

// SuffixTree1.cpp: implementation of the CSuffixTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SuffixTree.h"
#include "SuffixTree1.h"
#include "string.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CSuffixTree::CSuffixTree()
{
	m_Root = new Node;
	m_Root->Child =m_Root->Sibling = NULL;
	m_Root->i =m_Root->j = -1;
	m_S = "";
}

CSuffixTree::~CSuffixTree()
{
	FreeST(m_Root);
	if(SuffixArray)
		delete SuffixArray;
}

void CSuffixTree::NaiveMethod()
{
	int i,j,k,l,ii;
	Node *p,*q;
	p = new Node;
	p->i = 0;
	p->j = m_Len-1;
	p->Child = NULL;
	p->Sibling = NULL;
	m_Root->Child = p;
	for(i = 1; i < m_Len; i++)
	{
		j = ii = i;
		p = m_Root->Child;
		do
		{
			k = p->i;
			while((k<=p->j)&&(j<m_Len)&&(m_S[j]==m_S[k]))
			{
				j++;
				k++;
			}
			q = p;
			if(k>p->j && j<m_Len)
			{	
				p = p->Child ;
				ii = j;
			}
			else if(ii!=j)
				break;
			else 
				p = p->Sibling;
		}while(p);	
		p = new Node;
		if(ii==j)
		{
			p->i = ii;
			p->j = m_Len-1;
			q->Sibling = p;
			p->Child = p->Sibling =NULL;

		}
		else if(j < m_Len)
		{
			l = q->j;
			q->j = k - 1;
			p->Child = q->Child;
			q->Child = p;
			p->i = k;
			p->j = l;
			q = p;
			p = new Node;
			p->i = j;
			p->j = m_Len-1;
			p->Child = p->Sibling =NULL;		
			q->Sibling =p;
		}
	}
}

void CSuffixTree::FreeST(Node* p)
{
	Node* q,*r;
	if(p)
	{
		q = p->Child;
		while(q)
		{
			r = q;
			q = q->Sibling;
			FreeST(r);
		}
		delete p;
	}	
}

void CSuffixTree::Ukkonen()
{
	int i,j;
	Node *p;
	p = new Node;
	p->i = 0;
	p->j = 0;
	p->Child = NULL;
	p->Sibling = NULL;
	m_Root->Child = p;
	for(j = 0; j < m_Len - 1 ; j++)
		for(i = 0; i <=j+1 ; i++)
		{
			entension(i,j);
		}
}

void CSuffixTree::entension(int i, int j)
{
	int k,jj,ii;
	Node* p,*q,*r;
	if(m_Root)
		p = m_Root->Child; 
	else 
		return;
	r = m_Root;
	p = m_Root->Child;
	ii = jj = i;
	do
	{
		k = p->i;
		while((k <= p->j) && (jj <= j) && (m_S[jj] == m_S[k]))
		{
			k++;
			jj++;
		}
		q = p;
		if( k == p->i )
			p = p->Sibling ;
		else if( k <= p->j )
			break;
		else if(p->Child)
		{	
			r = p;
			p = p->Child;
			ii = jj;
		}
		else 
			break;
	}while(p);
	if(p==NULL)
	{
		p = r->Child;
		while(p)
		{
			if(m_S[p->i] == m_S[jj])
				return;
			else 
			{	
				q = p;
				p = p->Sibling;
			}
		}
		p = new Node;
		p->Child = p->Sibling = NULL;
		p->i = p->j = jj;
		q->Sibling = p;
		return;
	}
	if( k <= p-> j)
	{
		if(m_S[j + 1]==m_S[k]) return;
		p = new Node;
		p->i = k;
		p->j = q->j;
		p->Child = q->Child ;
		q->Child = p;
		q->j = k - 1;
		q = p;
		p = new Node;
		p->i = j + 1;
		p->j = j + 1;
		p->Child = p->Sibling =NULL;
		q->Sibling = p;
	}
	else if(jj > j)
	{
		q->j = j + 1;
	}
}

void CSuffixTree::SufArray()
{
	int temp;
	SuffixArray = new int[m_Len];
	for(int i = 0; i < m_Len; i++)
		SuffixArray[i] = i;	
	for(i = 0; i < m_Len; i++)
	{
		for(int j = i + 1; j < m_Len ; j++)
		{
			if(strcmp(m_S + SuffixArray[i], m_S+SuffixArray[j]) > 0)
			{
				temp = SuffixArray[i];
				SuffixArray[i] = SuffixArray[j];
				SuffixArray[j] = temp;
			}
		}
	}
}

void CSuffixTree::ConstructST(char *S,int m)
{
	m_S = S;
	m_Len = strlen(S);
	SufArray();
	if(m_Len==0)return;
	if(m == 0)
		Ukkonen();
	else
		NaiveMethod();
}