dict.cpp

设计并实现解字典问题的O(nlogn)时间算法

#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(const String& s);
  	~String() {delete[] str; delete[] pre;}
  	String& operator=( String& s);
  	bool operator== (const String& s)
  	{ 
  		if(s.length()==length())
  			return strcmp(str,s.str)==0;
  		return false;
  	}
  	int length()const {return size-1;}
  	int find(char c,int start);
  	void Delete(int index,int count);
  	int add();
  	//int readString();
  	int readString();
      void display()
  	{
  		if(size==1)
  		{
  			cout<<"String's display error!"<<endl;
  			throw "error";
  		}
  		out<<str<<' ';
  	}
  //private:
  	char *str;
  	int  *pre;
  	int  size;
  };
  
  String::String(char *s)
  {
  	size=strlen(s)+1;
  	str=new char[size];
  	if(str==0)  throw "error";
  	strcpy(str,s);
  	pre=new int[size];
  	if(pre==0)  throw "error";
  }
  
  String::String(const String&s)
  {
  	size=s.size;
  	str=new char[size];
  	if(str==0) throw "error";
  	strcpy(str,s.str);
  	pre=new int[size];
  	if(pre==0) throw "error";
  }
  String& String::operator=(String&s)
  {
  	if(s.size!=size)
  	{
  		delete[] str;
  		str=new char[s.size];
  		if(str==0)
  			throw "error";
  		size=s.size;
  	}
  	strcpy(str,s.str);
  	return *this;
  }
  
  int String::find(char c,int start)
  {
  	int ret;
  	char *p;
  	p=strchr(&str[start],c);
  	if(p!=0)
  		ret=int(p-str);
  	else
  		ret=-1;
  	return ret;
  }
  
  
  void String::Delete(int index,int count)
  {
  	int left=size-index-1,n,i;
      char *newstr,*p,*q;
  	if(index>=size-1)
  		return;
  	if(count>left)
  		count=left;
  	n=size-count;
  	newstr=new char[n];
  	if(newstr==0)
  		throw "error";
  	for(i=0,p=newstr,q=str;i<=index-1;i++)
  		*p++=*q++;
  	q+=count;
  	strcpy(p,q);
  	delete[] str;
  	size=n;
  	str=newstr;
  }
  
  int String::readString()
  {
  	char tmp[300],c='\0',s;
  	int i=0;
  	s=in.peek();
  	if(s<0)
  		goto end;
  	if(s=='\n')
  	{
  		in>>s;
  		if(s=='\n')
  			goto end;
  		else
  		{
  			tmp[i]=s;
  			i++;
  		}
  	}
  	while(c!=' '&&c!='\n'&&c>=0)
    {
  	    in>>c;
  		tmp[i]=c;
  		i++;
  		c=in.peek();
  	}
  	tmp[i]='\0';
  	delete[] str;
  	size=strlen(tmp)+1;
  	str=new char[size];
  	if(str==0)
  		throw "error";
  	strcpy(str,tmp);
  	return size-1;
  end:	return 0;
  }
  int String::add()
  {
  	int i,a=0;
  	for(i=0;i<size;i++)
  		a+=str[i];
  	return a;
  }
  
  
  template<class T>
  class list
  {
  	private:
  		int n,maxsize,m;
  		String  *data;
  	public:
  		list(int max=300);
  		~list();
  		void read();
  		int length();
  		int locate(T&x);
  		bool retrieve(int k,T&x);
  		list<T>& insert(int k, T&x);
  		void clearlist();
  };
  template<class T>
  list<T>::list(int max)
  {
  	maxsize=max;
  	data=new String [maxsize];
  	n=maxsize;
  	m=0;
  }
  template<class T>
  void list<T>::read()
  {
  	data[0].readString();
  }
  template<class T>
  list<T>::~list()
  {
  	delete[] data;
  }
  
  template<class T>
  void list<T>::clearlist()
  {
  	delete[] data;
  }
  template<class T>
  int list<T>::length()
  {
  	return m;
  }
  
  template<class T>
  int list<T>::locate(T&x)
  {
  	for(int i=0;i<m;i++)
  		if(data[i]==x)
  			return i;
  	return m;
  }
  
  template<class T>
  bool list<T>::retrieve(int k,T&x)
  {
  	if(k<1||k>m)
  		return false;
  	x=data[k-1];
  	return true;
  }
  
  template<class T>
  list<T>& list<T>::insert(int k,T&x)
  {
  	if(k<0||k>n)
  	{
  		cout<<"list's insert error";
  		throw "error";
  	}
  	if(m==n)
  	{
  		cout<<"list's insert error";
  		throw "error";
  	}
  	for(int i=m-1;i>=k;i--)
  		data[i+1]=data[i];
  	data[k]=x;
  	m++;
  	return *this;
  }
  
  template<class T>
  int hashf(T &x)
  {
  	return x.add()%300;
  }
  template<class T>
  class OpenHashTable
  {
  	public:
  		OpenHashTable(int n,int hashf(T &x));
  		~OpenHashTable(){clear();}
  		bool member(T& x,int &i,int &j);
  		OpenHashTable<T>& insert(T& x,int i,int j);
  		void display(int i,int j);
  	private:
  		void clear();
  		int size;
  		int (*hf)(T& x);
  		list<T> *ht;  
  };
  template<class T>
  OpenHashTable<T>::OpenHashTable(int n,int hashf(T& x)):size(n),hf(hashf),ht(new list<T>[size])
  {
  	
  }
  
  template<class T>
  void OpenHashTable<T>::clear()
  {
  	for(int i=0;i<size;i++)
  		ht[i].clearlist();
  }
  template<class T>
  bool OpenHashTable<T>::member(T& x,int &i,int &j)
  {
  	i=int(hf(x)%size);
  	j=ht[i].locate(x);
  	if(j<ht[i].length())
  		return true;
  	return false;
  }
  template<class T>
  void OpenHashTable<T>::display(int i,int j)
  {
  	if(i<0||i>=size)
  	{
  		cout<<"Table's display error!"<<endl;
  		throw "error";
  	}
  	ht[i].display(j);
  }
  template<class T>
  OpenHashTable<T>& OpenHashTable<T>::insert(T& x,int i,int j)
  {
  	ht[i].insert(j,x);
  	return *this;
  }
  int main()
  {
  	if(in.fail())
  	{
  		cout<<"the input.txt is not exist!";
  		exit(1);
  	}
  	OpenHashTable<String> t1(101,hashf),t2(101,hashf);
   
  	String s;
  	int a[300][300];
  	int i,j;
  	for(i=0;i<300;i++)
  		for(j=0;j<300;j++)
  			a[i][j]=0;
  	
  	int h=0,l=0,m,n;
	in>>m;
    int c=in.peek();
  	while((h<m)&&(s.readString()))
  	{
  		if(!t1.member(s,i,j))
           t1.insert(s,i,j);
		h++;
	}
	in>>n;	
	while((l<n)&&(s.readString()))	
	{
		if(!t1.member(s,i,j))
		{
			if(t2.member(s,i,j))
              a[i][j]++;
  		    else
			{
  			  t2.insert(s,i,j);
              a[i][j]=1;
			}
		}
		l++;
  		
  	}
  	int max=0;
	for(i=0;i<300;i++)
  		for(j=0;j<300;j++)
  			if((a[i][j]!=0)&&(a[i][j]>max))
				max=a[i][j];
    out<<max<<endl;
  	return 1;
  }