repeat.cpp

来自「设计一个算法」· C++ 代码 · 共 108 行

#include <iostream>
#include <fstream>
#include <string.h>  
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

class String
{
public: 
	String(char *s=""); 
	String(String &s);
	~String();
	int ReadString();
	int String::Length();
	int Prefix();
	void String::LongestMatch();//最长重复子串求解函数
private:
	char *str;	
	int *pre;
	int size; 
};

String::String(char *s)
{
	size=strlen(s)+1;
	str=new char[size];
	if(str==0) throw;
	strcpy(str,s);
	pre=new int[size];
	if(pre==0) throw; 
}

String::String(String &s)
{
	size=s.size;
	str=new char [size];
	if(str==0)
		throw;
	strcpy(str,s.str);
	pre=new int[size];
	if(pre==0)
		throw;
}

String::~String()
{
	delete[]str;
	delete[]pre;
}

int String::ReadString()
{
	char source[1000000];
	delete[]str;
	in>>source;
	size=strlen(source)+1;
	str=new char[size];
	if(str==0) throw;
	strcpy(str,source);
	return size-1;
}

int String::Length()
{
	return size-1;
}

 
void String::LongestMatch()
{
	
	int mlength=0,count=0;
	
	int first;
	for(int i=1;i<=Length();i++)
	{
		for(int k=0,j=0;j<=Length()-i;j++)
		{
			if(str[j]==str[i+j]) k++; 
			else k=0;
			if(k>mlength)
			{
				first=j-k+1; 
				mlength=k;
			}
		}
	} 
	out<<mlength<<endl;
	if(mlength)
	{
		for(i=first;count<mlength;i++)
		{
			out<<str[i];
			count++;
		}
	}  
}

void main()
{
	
	
	String str;
	str.ReadString();
    str.LongestMatch();	
}