kmp算法.txt

KMP算法是一个查找两个字符串公共串的算法,比一般的算法效率要高很多.

#ifndef_CMyString_
#define _CMyString_
#define MAX_STRING_SIZE 1024
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();
  int Find(const 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)
    {
        memcmp(str+length,s->str+1);
        length+=s->length;
    }
    else
    {
        cout<<"error,string length overflow!"<<endl;
        
    }
}
//////////////
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+len,length-pos+1);
}            
             
Cmystring::GenKMPNext(int *next, CMyString *s)
{ int i=0;j=-1;
   next[0]=-1;
 while(i<s->length)
  {
  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(const CMyString * s)
{
   int i, j, *next=new int[s->length];
    GenKMPNext(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;
   }
}

//////////////
int main()
{
    char *p,*t;
    cin>>p;
    Cmystring a(p);
    cin>>t;
    int c=a.Find(t);
    cout<<c<<endl;
    return 0;
}