count-姜.cpp

设计一个算法

#include<iostream>
#include<string>
#include<fstream>
int *pre;
void prefix(std::string &str)
{
    int m=str.length();
    pre=new int[m+1];
    pre[1]=0;
    int k=0;
    for(int i=2;i<=m;i++){
        while(str[i-1]!=str[k] && k>0)k=pre[k];
        if(str[i-1]==str[k])pre[i]=++k;
        else pre[i]=0;
    }
}
int match(std::string &s,std::string &t)
{
    int i=0,j=0,count=0;
    int n=s.length(),m=t.length();
    prefix(t);
loop:
    while(i<n && j<m){
        if(s[i]==t[j]){
            i++;
            j++;
        }
        else{
            if(j==0)i++;
            else j=pre[j];
        }
    }   
    if(j>=m && i<n){
        count++;
        j=0;
        goto loop;
    }
return count;	
}
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);
    }
    string s,t;
    char c;
    char file[100];
    fin.getline(file,100);
    getline(fin,t);
    ifstream temp(file);
    while((c=temp.get())!=EOF)
        s+=c;
    fout<<match(s,t)<<endl;
    fin.close();
    fout.close();
    temp.close();
    return 0;
}