count.cpp

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

#include"iostream.h"
#include"fstream.h"
#include"stdlib.h"
#include "string.h"
class String
{
public:
	String(){str=0;}//构造函数很重要
    void  ring(char *string,unsigned aim);//新串的读入
	~String();
	int check(char *string,unsigned aim,char *aimstring);
	void aimstr(char *substring);
	char *str;
private:
	int *pre;
	int checknumber;
	unsigned num;
    char *temp;
};
void String::ring(char *string,unsigned aim)//aim是要检测数的长度……………………成功
{  
    
	unsigned a;
	temp=new char[aim];
	
	if(str==0){
	str=new char[500];
    strcpy(str,string);
	goto loop;
}
    a=strlen(str);
	
	if(a<aim){
	strcat(str,string);
	
	}
	else{
	strrev(str);
	for(num=0;num<aim-1;num++){
    temp[num]=str[aim-2-num];
	}
    temp[aim-1]='\0';//串尾符号
	strcpy(str,temp);
	strcat(str,string);
	}

loop:;
}
String::~String()
{
	delete[]str;
}
void String::aimstr(char *aimstring){//成功
    int length,temp,i,checkin=1;
	temp=length=strlen(aimstring);
	temp=temp-1;
	pre=new int[length];
    pre[0]=0;
	if(length==1)pre[0]=0;
	else{
		while(temp>0){
			for(i=0;i<temp;i++){
				if(aimstring[length-temp+i]==aimstring[i]){
					
					pre[length-temp+i]=checkin;
					checkin++;
				}
				else{
					pre[length-temp]=0;
					checkin=1;
				    temp--;
					i=0;
					break;
				}
			
			}	
			if(checkin==temp+1){
					break;}
		}
	}


}
int String::check(char *string,unsigned aim,char *aimstring){
	unsigned length,i,time=0,aimtime=0;
	ring(string,aim);
    checknumber=0;
	aimstr(aimstring);
	length=strlen(str);
	if(length<aim){
		goto end;

}
    for(i=0;i<length;i++)
	{
         if(i==length&&aimtime!=aim-1)
		 {goto end;
		 }
loop:  if(str[i]==aimstring[aimtime])
	   {
         time++;
		 aimtime++;
	   }
	   else{
		   if(aimtime==0){}
		   else{
			   aimtime=pre[aimtime-1];
			   time=pre[aimtime];//pre[]已经表示前面有几个是相同的了！！！
			   goto loop;
		   }
	   }
	   if(time==aim)
	   {
		 checknumber++;
		 aimtime=0;
		 time=0;
	   }
		
	}
    
end: return checknumber;
}

void main()
{
    unsigned aim,a=0,temp,checknumber=0; 
	char *str1=new char[50],*str2=new char[50],*str3=new char[500];
    ifstream in("input.txt");
	ofstream out("output.txt");
	String string;
	in.getline(str1,50,'\n');
    in.getline(str2,50,'\n');
	
	aim=strlen(str2);
    ifstream inout(str1);
    while(!inout.fail()){
		inout.getline(str3,500,'\n');
		if(str3[0]==0 )
			continue;
        temp=string.check(str3,aim,str2);
        checknumber=checknumber+temp;
		
         
	}
	out<<checknumber;
}