蓝桥杯基础算法训练字串统计（STL vector 的运用）

朴灿烈づ我的快乐病毒、 2022-03-21 14:10 174阅读 0赞

问题描述

给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

输入格式

第一行一个数字L。  
　　第二行是字符串S。  
　　L大于0，且不超过S的长度。

输出格式

一行，题目要求的字符串。  
  
　　输入样例1：  
　　4  
　　bbaabbaaaaa  
  
　　输出样例1：  
　　bbaa  
  
　　输入样例2：  
　　2  
　　bbaabbaaaaa  
  
　　输出样例2：  
　　aa

数据规模和约定

n<=60  
　　S中所有字符都是小写英文字母。

提示

枚举所有可能的子串，统计出现次数，找出符合条件的那个

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    
    int main()
    {
    	int n,m,j,k,i,T;
    	int L;
    	string s;
    	vector<string>v1;
    	
    	
    	while (cin>>L)
    	{
    		cin>>s;
    		for (i=L;i<=s.size();i++)
    		{
    			for (j=0;j<=s.size()-i;j++)
    			{
    				v1.push_back(s.substr(j,i));
    			}
    		}
    		
    		vector<int>v2(v1.size());//记住,一定要初始化 
    		
    		for (i=0;i<v1.size();i++)
    		{
    			for (j=0;j<v1.size();j++)
    			{
    				if (i!=j && v1[i]==v1[j])
    				v2[i]++;
    			}
    		}
    		
    		int max=0,k=0;
    		for (i=0;i<v1.size();i++)
    		{
    			if (v2[i]>max || (v2[i]==max&&  v1[i].size() > v1[k].size()) )
    			{
    				k = i;
    				max = v2[i];
    			}
    		}
    		cout<<v1[k]<<endl;
    	}
    	
    	
    	return 0;
    }