count1.cpp

记数问题

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
class String
{
public:
	String(char *s="");
    void Build(char *s);
	~String();
	int Length() const;
	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];
}
void String::Build(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;
}
void String::Prefix()
{
	int m=Length();
	delete[] pre;
	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 String::Match(String& t)
{
	int i=1,j=0;
	int num=0;
    int n=Length(),m=t.Length();
    t.Prefix();
    while((i<=n)&&(j<m))
	{
		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 main()
{
	int num=0;
	String s,patten;
    char text[100],str[200],read[10000];
	in.getline(text,100);
    in.getline(str,200);
	patten.Build(str);
    ifstream fin(text);
	while(fin.getline(read,sizeof(read)))     
	{
		s.Build(read);
		num=num+s.Match(patten);
	}
	out<<num;
}