count2.cpp

记数问题

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
    public:
		String(char *s="");
		~String();
		int Length() const;
        void Make(char *s);
		void Prefix();
		int Match(String& t);
	private:
		char *str;
		int *pre;
		int size;
};
String::String(char *s)
{ 
    size=strlen(s)+1;
	str=new char [size];
	strcpy(str,s);
	pre=new int[size];
}
  
String::~String()
{
	delete[]str;
	delete[]pre;
}
int String::Length()  const
{
	return size-1;
}
int String::Match(String & t)
{
	int i=1,j=0,n,m,num=0;
	n=Length(),m=t.Length();
	t.Prefix();
	while(i<=n)
	{
		if(str[i-1]==t.str[j])
		{
			i++;
			j++;
			if(j==m) 
			{
				num++;
				j=0;
			}
		}
		else
			if(j==0) i++;
			else j=t.pre[j];
	}
	return num;
}

void String::Prefix()
{
    int m=0;
    m=Length();
	delete[]pre;
	pre=new int[m+1];
	pre[1]=0;
	int k=0;
	int i=0;
	for(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;
	}
}
void String::Make(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
	strcpy(str,s);
	pre=new int[size];
}
void main()
{
	String S0,S;
	int num=0;
	char a[1000];
	char define[50],b[100];
	in.getline(define,50);
	in.getline(b,100);
	S.Make(b);
	ifstream fin(define);
	while(fin.getline(a,1000))
	{
		S0.Make(a);
		num+=S0.Match(S);	
	}
	out<<num<<endl;
}