cmystring.h

kmp算法

#include"memory.h"
#include<iostream.h>
#define MAX_STRING_SIZE 4096

class CMyString
{
  private:
      int length;
      char str[MAX_STRING_SIZE+1];//存储
  public:
      CMyString();
      CMyString(const char *s);
      ~CMyString();   
	  Concatenate(const CMyString *s);
      Insert(const int pos, const CMyString *s); //插入
      Delete(const int pos, const int len);//删除
      CMyString Substring(const int pos, const int len);//提取子字符串
      char *GetString();
      int GetLength();
	  void GetKMPNext(int *next, CMyString *s);//获取next的值
      int Find( CMyString *s);//查找
};
CMyString::CMyString()
{
	length=0;
	str[0]=0;
}
CMyString::CMyString(const char* s)
{
	 char *p1,*p2;
	 for(length=0,p1=str,p2=(char*)s;*p2;length++)
		 *p1++=*p2++;
	 *p1=0;
}
CMyString::~CMyString()
{}
CMyString::Concatenate(const CMyString*s)
{
	if(length+s->length<=MAX_STRING_SIZE)
	{
		memcpy(str+length,s->str,s->length+1);
		length+=s->length;
	}
	else
	{
		cout<<"error: string length overflow!";
	}
}
CMyString::Delete(const int pos,const int len)
{
	int rlen=len;
	if(pos+rlen>length)
	{
	   rlen=length-pos;
	}
	length-=rlen;
	memcpy(str+pos,str+pos+rlen,length-pos+1);
}

int CMyString::GetLength()
{
	return length;
}
char* CMyString::GetString()
{
	char* tmpStr = new char[length+1];
	memcpy(tmpStr,str,length+1);
	return tmpStr;
}
CMyString::Insert(const int pos,const CMyString * s)
{
	if(length + s ->length<=MAX_STRING_SIZE)
	{
		memcpy(str+pos+s ->length,str+pos,length-pos+1);
		memcpy(str+pos,s->str,s->length);
		length+=s->length;
	}
	else
	{
		cout<<"error:string length overflow !";
	}
}
CMyString CMyString::Substring(const int pos,const int len)
{
	int rlen=len;
	CMyString tmpStr("");
	if(pos+len>length)
		rlen=length-pos;
	memcpy( tmpStr.str,str+pos,rlen);
	tmpStr.length=rlen;
	 tmpStr.str[ tmpStr.length]=0;
	 return  tmpStr;
}




void CMyString::GetKMPNext(int *next, CMyString *s)
{ int i=0,j=-1;
   next[0]=-1;
 while(i<(*s).GetLength())
  {
  while(j>=0&&s->str[i]!=s->str[j])
     j=next[j];
   i++;j++;
   if(s->str[i]==s->str[j])
      next[i]=next[j];else  next[i]=j;}
}

 int CMyString::Find( CMyString * s)
{
   int i, j, *next=new int[s->length];
    GetKMPNext(next,s);
     for(i=0,j=0;i<s->length&&j<length;)
      {
		        if(s->str[i]==str[j]){i++;j++;}
       else
           if(next[i]>=0)
                i=next[i];
            else {i=0;j++;}  
       }
        if(i>=s->length)
          return j-s->length;
        else   
        return -1;
 }