频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
数据结构_串_串的_KMP算法_C++实现
2011-09-17 14:00:37      个评论      
收藏   我要投稿

"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; 
        } 
    } 

作者“Dreamer Thinker Doer”
 

点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 算法
上一篇:虚函数表对C++了解的人都应该知道虚函数
下一篇: C++的标识符
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站