蓝桥杯算法训练字串统计 By Assassin 字符串操作+离散化

2019-11-06 06:19:27

字体：大中小

来源：转载

供稿：网友

问题描述　　给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式　　第一行一个数字L。　　第二行是字符串S。　　L大于0，且不超过S的长度。输出格式　　一行，题目要求的字符串。　　输入样例1：　　4　　bbaabbaaaaa　　输出样例1：　　bbaa　　输入样例2：　　2　　bbaabbaaaaa　　输出样例2：　　aa数据规模和约定　　n<=60　　S中所有字符都是小写英文字母。提示　　枚举所有可能的子串，统计出现次数，找出符合条件的那个

其实这道题是一个简单的字符串操作，只不过在处理这个问题的时候用到了一下小技巧，比如string字符串操作，map迭代器的使用，简单的离散化思想，和自定义的sort函数，对于新手还是值得学习一下的

首先我们明确数据范围就是n<=60，那么其实明显用字符串暴力记录就可以了，但是这里买你还有一定的规则，就是如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的

那么我是这么处理的，我们在记录string串用map 《string , int》，因为N<=60那么出现的最多次数不过是L=1，n=60吧！那么出现的次数最多60次吧，那么我们在处理int记录次数的时候，加上起点位置*一个大数 ，这个大数一定比60大，那么我们就可以记录该串起点的位置了，而且每次取个数的时候只需要模一下那个大数就能得到次数！ 然后用map迭代器找到出现最多的次数，用结构体记录出现次数最多的串，然后我们用一个cmp自定义函数排序，具体函数如下：

int cmp(node a,node b){ if(a.s.size()>b.s.size()) return 1; //先比大小 else if(a.s.size()==b.s.size()){ //大小相同则比较起点位置，即出现早晚，因为乘上一个大数，一定是越小越早出现！ if(a.times<b.times) return 1; } return 0;}

下面是我的丑代码，具体见注释~

#include<bits/stdc++.h>using namespace std;map<string,int>mp; typedef struct node{ string s; int times;}node;node ans[100001];int cmp(node a,node b){ if(a.s.size()>b.s.size()) return 1; //先比大小 else if(a.s.size()==b.s.size()){ //大小相同则比较起点位置，即出现早晚，因为乘上一个大数，一定是越小越早出现！ if(a.times<b.times) return 1; } return 0;}int main(){ int l; string target,temp; cin>>l>>target; for(int i=0;i<=target.size()-l;i++){ for(int j=l;j<=target.size()-i;j++){ temp.assign(target,i,j); if(mp[temp]==0){ //如果第一次出现初始化一个×大数的基底，离散化 mp[temp]=100000*i+1; } else{ mp[temp]++; } } } int maxnumber=0; map<string,int>::iterator it; //map迭代器 for(it=mp.begin();it!=mp.end();it++){ //求出来出现最多的次数 maxnumber=max(maxnumber,(it->second)%100000); //记得取模 } int pos=0; for(it=mp.begin();it!=mp.end();it++){ //将出现的次数最多的串信息记录下来 if(it->second%100000==maxnumber){ ans[pos].s.assign(it->first); ans[pos++].times=it->second; } } sort(ans,ans+pos,cmp); //排序 cout<<ans[0].s<<endl; return 0;}

上一篇：深入浅出JMS(1)--JMS基本概念

下一篇：pycharm的两种激活方法