程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構_串_串的_KMP算法_C++實現

數據結構_串_串的_KMP算法_C++實現

編輯：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
            <<"1 . Set Main String"<<endl
            <<"2 . Set SubString"<<endl
            <<"3 . KMP"<<endl
            <<"4 . Print"<<endl
            <<"5 . Quit"<<endl<<endl;
        cin>>choice;
        switch(choice)
        {
        case '1':
            str.GetString();
            break;
        case '2':
            str.GetSubString();
            break;
        case '3':
            str.KMP();
            break;
        case '4':
            str.Print();
            break;
        case '5':
            return 0;
        default:
            cout<<"No Such Choice !"<<endl;
            break;
        }
    }
}