数据结构_串_串的_KMP算法_C++实现

"head.h"

view plaincopy to clipboardprint?#include<iostream>  
#include<string>  
using namespace std; 
 
class STRING 
{ 
public: 
    void GetString(); 
    void GetSubString(); 
    void KMP(); 
    void Print(); 
private: 
    void GetNext(); 
    string str; 
    string sub; 
    int next[1000]; 
    int strlen; 
    int sublen; 
}; 
 
void STRING::GetString() 
{ 
    cout<<"Please Input The MainString :"<<endl<<endl; 
    cin>>str; 
    strlen=str.length(); 
} 
 
void STRING::GetSubString() 
{ 
    cout<<"Please Input The SubString :"<<endl<<endl; 
    cin>>sub; 
    sublen=sub.length(); 
} 
 
void STRING::KMP() 
{ 
    cout<<"KMP Method Called !"<<endl<<endl; 
    GetNext(); 
    int i,j; 
    i=j=0; 
    while(i<strlen&&j<sublen) 
    { 
        if(j==-1||str[i]==sub[j]) 
        { 
            i++; 
            j++; 
        } 
        else 
        { 
            j=next[j]; 
        } 
    } 
    if(j==sublen) 
    { 
        cout<<"Succeed ! Position = "<<i-j+1<<endl<<endl; 
    } 
    else 
    { 
        cout<<"Failed !"<<endl<<endl; 
    } 
} 
 
void STRING::Print() 
{ 
    cout<<"Main String = "<<str<<endl<<"    Length = "<<strlen<<endl; 
    cout<<"SubString = "<<sub<<endl<<"    Length = "<<sublen<<endl<<endl; 
} 
 
void STRING::GetNext() 
{ 
    int i,j; 
    next[0]=-1; 
    i=0;j=-1; 
    while(i<sublen-1) 
    { 
        if(j==-1||sub[i]==sub[j]) 
        { 
            i++; 
            j++; 
            if(sub[i]!=sub[j]) 
                next[i]=j; 
            else 
                next[i]=next[j]; 
        } 
        else 
        { 
            j=next[j]; 
 
        } 
    } 
} 
#include<iostream>
#include<string>
using namespace std;

class STRING
{
public:
 void GetString();
 void GetSubString();
 void KMP();
 void Print();
private:
 void GetNext();
 string str;
 string sub;
 int next[1000];
 int strlen;
 int sublen;
};

void STRING::GetString()
{
 cout<<"Please Input The MainString :"<<endl<<endl;
 cin>>str;
 strlen=str.length();
}

void STRING::GetSubString()
{
 cout<<"Please Input The SubString :"<<endl<<endl;
 cin>>sub;
 sublen=sub.length();
}

void STRING::KMP()
{
 cout<<"KMP Method Called !"<<endl<<endl;
 GetNext();
 int i,j;
 i=j=0;
 while(i<strlen&&j<sublen)
 {
  if(j==-1||str[i]==sub[j])
  {
   i++;
   j++;
  }
  else
  {
   j=next[j];
  }
 }
 if(j==sublen)
 {
  cout<<"Succeed ! Position = "<<i-j+1<<endl<<endl;
 }
 else
 {
  cout<<"Failed !"<<endl<<endl;
 }
}

void STRING::Print()
{
 cout<<"Main String = "<<str<<endl<<"    Length = "<<strlen<<endl;
 cout<<"SubString = "<<sub<<endl<<"    Length = "<<sublen<<endl<<endl;
}

void STRING::GetNext()
{
 int i,j;
 next[0]=-1;
 i=0;j=-1;
 while(i<sublen-1)
 {
  if(j==-1||sub[i]==sub[j])
  {
   i++;
   j++;
   if(sub[i]!=sub[j])
    next[i]=j;
   else
    next[i]=next[j];
  }
  else
  {
   j=next[j];

  }
 }
}

"main.cpp"

view plaincopy to clipboardprint?#include<iostream>  
#include"head.h"  
using namespace std; 
 
int main() 
{ 
    STRING str; 
    char choice; 
    while(1) 
    { 
        cout<<"Your Choice Please ?"<<endl<<endl&nb

补充：软件开发 , C++ ,

上一个：C++的标识符
下一个：虚函数表对C++了解的人都应该知道虚函数