题目

You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X=x1x2…xn and Y=y1y2…ym be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or xj>yj where j is the smallest integer such that xj≠yj.

Constraints

• 1 ≤ |s| ≤ 5000
• s consists of lowercase English letters.
• 1 ≤ K ≤ 5
• s has at least K different substrings.

Partial Score

• 200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

sK

Output

Print the K-th lexicographically smallest substring of K.

题目大意

给你一个字符串s，求它字典序第k大的字串

分析

因为k<=5，所以我们可以枚举字串的起始点和长度，以为长度小，我们把整个字串转化成数字然后排序即可，注意长度不满k的字串在末尾要补零

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

long long a[110000];

map<long long,bool>app;

int cnt;

long long go(string s,int le,int ri){

    int i,j,k;

    long long res=0;

    for(i=le;i<=ri;i++)

        res=res*100+(s[i]-'a'+1);

    for(i=ri-le+2;i<=5;i++)    

        res*=100;

    return res;

}

int main()

{   int n,m,i,j,k;

    string s;

    cin>>s;

    n=s.length();

    cin>>k;

    for(i=0;i<n;i++)

        for(j=i;j<=min(i+k,n-1);j++){

            long long res=go(s,i,j);

            if(!app[res]){

                a[++cnt]=res;

                app[res]=1;

            }

        }

    sort(a+1,a+cnt+1);

    char c[110];

    cnt=0;

    while(a[k]){

        if(a[k]%100)c[++cnt]=(a[k]%100-1)+'a';

        a[k]/=100;

    }

    for(i=cnt;i>0;i--)

        cout<<c[i];

    return 0;

}