1335.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class item{
  public:
	  string s;
	  int n;
	  item(){}
	  item(string a,int b){s=a;n=b;}
};
int binarySearch(vector<item> & data,string value){
 int low=0;
 int high=data.size();
 while(low<high){
   int mid=(low+high)/2;
   if(data[mid].s==value) return mid;
   else if(data[mid].s<value)
        low=mid+1;
   else high=mid;
 }
 return low;
}
int cmp(const item & a,const item & b){
   if(a.n!=b.n) return a.n>b.n;
   else return a.s<b.s;
}
int main(){
   //ifstream cin("in.txt");
   string s,ss,temp;
   int i,j,k;
   vector<item> vec1,vec2,vec3,vec4,vec5;
   while(cin>>s){
       for(i=0;i<s.length();i++){
		   if(s[i]>='a'&&s[i]<='z') s[i]+=('A'-'a');
		   else if(!(s[i]<='Z'&&s[i]>='A')) s[i]=' ';
	   }
	   istringstream is(s);
	   while(is>>ss){
           k=ss.length();
		   for(i=0;i<k;i++){
			   if(k-i>=1) {temp=ss.substr(i,1); j=binarySearch(vec1,temp); if(j<vec1.size()&&vec1[j].s==temp) vec1[j].n+=1; else vec1.insert(vec1.begin()+j,item(temp,1));}
			   if(k-i>=2) {temp=ss.substr(i,2); j=binarySearch(vec2,temp); if(j<vec2.size()&&vec2[j].s==temp) vec2[j].n+=1; else vec2.insert(vec2.begin()+j,item(temp,1));} 
			   if(k-i>=3) {temp=ss.substr(i,3); j=binarySearch(vec3,temp); if(j<vec3.size()&&vec3[j].s==temp) vec3[j].n+=1; else vec3.insert(vec3.begin()+j,item(temp,1));}
			   if(k-i>=4) {temp=ss.substr(i,4); j=binarySearch(vec4,temp); if(j<vec4.size()&&vec4[j].s==temp) vec4[j].n+=1; else vec4.insert(vec4.begin()+j,item(temp,1));}
			   if(k-i>=5) {temp=ss.substr(i,5); j=binarySearch(vec5,temp); if(j<vec5.size()&&vec5[j].s==temp) vec5[j].n+=1; else vec5.insert(vec5.begin()+j,item(temp,1));}
		   }
	   }
   }
   sort(vec1.begin(),vec1.end(),cmp);
   sort(vec2.begin(),vec2.end(),cmp);
   sort(vec3.begin(),vec3.end(),cmp);
   sort(vec4.begin(),vec4.end(),cmp);
   sort(vec5.begin(),vec5.end(),cmp);
   cout<<"Analysis for Letter Sequences of Length 1\n-----------------------------------------\n";
   k=0;
   for(i=0;i<vec1.size();i++){
       if(k==5) break;
	   k++;
	   cout<<"Frequency = "<<vec1[i].n<<", Sequence(s) = ("<<vec1[i].s;
	   j=i+1;
	   while(j<vec1.size()&&vec1[j].n==vec1[i].n){
           cout<<","<<vec1[j].s;
		   j+=1;
	   }
	   if(j>i+1)i=j-1;
	   cout<<")\n";
   }
   cout<<"\nAnalysis for Letter Sequences of Length 2\n-----------------------------------------\n";
   k=0;
   for(i=0;i<vec2.size();i++){
       if(k==5) break;
	   k++;
	   cout<<"Frequency = "<<vec2[i].n<<", Sequence(s) = ("<<vec2[i].s;
	   j=i+1;
	   while(j<vec2.size()&&vec2[j].n==vec2[i].n){
           cout<<","<<vec2[j].s;
		   j+=1;
	   }
	   if(j>i+1)i=j-1;
	   cout<<")\n";
   }
   cout<<"\nAnalysis for Letter Sequences of Length 3\n-----------------------------------------\n";
   k=0;
   for(i=0;i<vec3.size();i++){
       if(k==5) break;
	   k++;
	   cout<<"Frequency = "<<vec3[i].n<<", Sequence(s) = ("<<vec3[i].s;
	   j=i+1;
	   while(j<vec3.size()&&vec3[j].n==vec3[i].n){
           cout<<","<<vec3[j].s;
		   j+=1;
	   }
	   if(j>i+1)i=j-1;
	   cout<<")\n";
   }
   cout<<"\nAnalysis for Letter Sequences of Length 4\n-----------------------------------------\n";
   k=0;
   for(i=0;i<vec4.size();i++){
       if(k==5) break;
	   k++;
	   cout<<"Frequency = "<<vec4[i].n<<", Sequence(s) = ("<<vec4[i].s;
	   j=i+1;
	   while(j<vec4.size()&&vec4[j].n==vec4[i].n){
           cout<<","<<vec4[j].s;
		   j+=1;
	   }
	   if(j>i+1)i=j-1;
	   cout<<")\n";
   }
   cout<<"\nAnalysis for Letter Sequences of Length 5\n-----------------------------------------\n";
   k=0;
   for(i=0;i<vec5.size();i++){
       if(k==5) break;
	   k++;
	   cout<<"Frequency = "<<vec5[i].n<<", Sequence(s) = ("<<vec5[i].s;
	   j=i+1;
	   while(j<vec5.size()&&vec5[j].n==vec5[i].n){
           cout<<","<<vec5[j].s;
		   j+=1;
	   }
	   if(j>i+1)i=j-1;
	   cout<<")\n";
   }
   cout<<endl;
}