Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这样也能过。

Posted by 350053879 at 2007-05-15 17:47:08 on Problem 1580
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

//vector<string>v;
//vector<string>::iterator t;

int gcd(int a,int b)
{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}


int matching_through(string a,string b,int i)
{
	//从b的第i个匹配	
	int s1=0;
	int s2=i;	
    int max=0;
	
    for(s1=0;s1<a.size();s1++)         
	{
		int temp=s1;
		int num=0;

		while(temp<a.size())              //如果超过了a的长度
		{
			for(s2=i;s2<=b.size()-1;s2++)
			{
				if(b[s2]==a[temp])
				{
					num++;
				}
				temp++;
			}
		}
		if(num>max) max=num;
	}
	return max;
}

int main()
{
	string a,b;
	
	while(cin>>a)
	{
		if(a=="-1") break;
		cin>>b;
		//	cout<<a<<endl;		cout<<b<<endl;
		int max=0;

		for(int i=0;i<b.size();i++)             //复杂度为O((a.size())^2*(b.size())^2)
		{
			int num;

			num=matching_through(a,b,i);

			if(num>max){
				max=num;
			}
		}

		max*=2;

		if(max==0||max==a.size()+b.size())
		{
			max=max/(a.size()+b.size());
			cout<<"appx("<<a<<","<<b<<") = "<<max<<endl;			
		}

		else
		{
			int temp=gcd(max,a.size()+b.size());
			int res2;

			max/=temp;

			res2=(a.size()+b.size())/temp;     //jianhua 

			cout<<"appx("<<a<<","<<b<<") = "<<max<<"/"<<res2<<endl;

		}
	}
	
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator