Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这样也能过。#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator