博客

问题描述


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

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

用map记录<子串，<出现次序，次数>>

最后遍历map，比较更新。

lqb不支持auto

#include<bits/stdc++.h>

using namespace std;

string str;

map<string,pair<int,int> > mp;

int main(){
    int l;
    scanf("%d",&l);
    cin>>str;
    int len = str.length();
    int id=0;
    for(int i=l;i<=len;i++){
        for(int st=0;st<len-i+1;st++){
            // printf("%s\n",str.substr(st,i).c_str());
            if(mp[str.substr(st,i)].second){
                mp[str.substr(st,i)].second++;
            }else{
                mp[str.substr(st,i)] = make_pair(id++,1);
            }
        }
    }
    
    map<string,pair<int,int> >::iterator it = mp.begin();
    
    string S= "";//答案
    int T=-1;//次数
    int ID = 1e9;//出现次序
    int L=0;//长度
    
    while(it!=mp.end()){
        string s = (it->first);
        int id = (it->second).first;
        int t = (it->second).second;
        int l = s.length();
        // printf("%s %d %d\n",s.c_str(),id,t);
        if(t>T){
            S = s;
            T=t;
            ID = id;
            L = l;
        }else if(t==T){
            if(l>L){
                S = s;
                L=l;
                ID = id;
            }else if(l == L){
                if(id<ID){
                    S = s;
                    ID = id;
                }
            }
        }
        it++;
    }
    printf("%s\n",S.c_str());

 return 0;
}

输入格式 　　L S

L大于0，且不超过S的长度。

输入样例1：

4

bbaabbaaaaa

输出样例1：

bbaa

输入样例2：

2

bbaabbaaaaa

输出样例2：

aa