gap.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream>
#include<fstream>
#include<string>
class Gap{
    private:
        std::string s;
        std::string p;
        int *next;
        void getnext();
   //     void improve();
    public:
        Gap(){};
        ~Gap(){/*for(int i=1;i<=p.length();i++)std::cout<<next[i]<<" "*/;delete []next;}
        void input(std::ifstream &fin);
        bool kmp_match();
};
void Gap::getnext()
{
    int len=p.length();
    next=new int [len+1];
    next[1]=0; 
    int k=0;   
    for(int i=2;i<=len;i++){
        if(p[i-1]=='*')continue;
        if(p[i-2]=='*'){
            next[i]=i-1;
            k=i-1;
            continue;
        }        
        while(k>0 && p[i-1]!=p[k] && p[k-1]!='*')k=next[k];
        if(p[i-1]==p[k] || k>0 && p[k-1]!='*')next[i]=++k;
        else next[i]=k;
    }
}
/*void Gap::improve()
{
    getnext();
    int m=p.length();
    int *f=new int[m+1];
    for(int i=1;i<=m;i++)f[i]=next[i];
    for(int i=1;i<m;i++){
        if(p[i-1]=='*')continue;        
        int k=f[i+1];
        if(k==0 && p[k-1]!='*' || p[i]!=p[k])next[i]=k;
        else
            next[i]=next[k];
    }
    delete []f;
}*/
inline void Gap::input(std::ifstream &fin)
{
    std::getline(fin,s);
    std::getline(fin,p);
}
bool Gap::kmp_match()
{
    int i=0,j=0;
    int n=s.length(),m=p.length();
  //  improve();
    getnext();
    while(i<n && j<m){
        if(p[j]=='*'){
            j++;
            continue;
        }
        if(s[i]==p[j]){
            i++;
            j++;
        }
        else{
            if(j==0 || p[j-1]=='*')i++;
            else j=next[j];
        }
    }
    if(j<m){
        if(i>=n){
            while(j<m){
                if(p[j++]!='*')
                    return false;                
            }
            return true;
        }
        return false;
    }
    return true;
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"input.txt is not exist"<<endl;
        exit(1);
    }
    Gap g;
    g.input(fin);
    if(g.kmp_match())
        fout<<"Yes"<<endl;
    else
        fout<<"No"<<endl;
  //  g.~Gap();
  //  cin.get();    
    fin.close();
    fout.close();
	return 0;
}