Submission #2500578

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int maxn = 5050;
string s;
int k, cnt[26];
set<string> Set;
string ans[maxn];
vector<int> pos, t;

int main()
{
    cin >> s >> k;
    int n = s.size();
    if(n < 50) {
        for(int i = 0; i < n; i ++) {
            for(int j = 1; j <= n - i; j ++) {
                if(Set.size() <= k)
                    Set.insert(s.substr(i, j));
                if(Set.size() > k) {
                    auto it = Set.end();
                    it --;
                    Set.erase(it);
                }
            }
        }
        cout << *(Set.rbegin());
    } else {
        int mn = 1e9;
        for(int i = 0; i < n; i ++)
            cnt[s[i] - 'a'] ++;
        for(int i = 0; i < 26; i ++) {
            if(!cnt[i])
                continue;
            Set.clear();
            bool flag = false;
            for(int j = 0; j < n; j ++) {
                if(s[j] - 'a' == i) {
                    for(int len = 1; len <= n - j; len ++) {
                        Set.insert(s.substr(j, len));
                        if(Set.size() >= k) {
                            flag = true;
                            goto finish;
                        }
                    }
                }
            }
finish:
            if(!flag) {
                k -= Set.size();
            } else {
                mn = i;
                break;
            }
        }

        for(int i = 0; i < n; i ++)
            if(s[i] - 'a' == mn)
                pos.push_back(i);
        bool flag = false;
        for(int i = 1; i <= k; i ++) {
            if(pos.size() == 1) {
                for(int j = pos[0] - i + 1; j <= pos[0] - i + k; j ++)
                    cout << s[j];
                flag = true;
                break;
            } else {
                t.clear();
                int mn = 1e9;
                for(int j = 0; j < pos.size(); j ++)
                    if(pos[j] + 1 < n)
                        mn = min(mn, s[pos[j] + 1] - 'a');
                for(int j = 0; j < pos.size(); j ++)
                    if(pos[j] + 1 < n && mn == s[pos[j] + 1] - 'a')
                        t.push_back(pos[j] + 1);
                pos.clear();
                for(int j = 0; j < t.size(); j ++)
                    pos.push_back(t[j]);
            }
        }
        if(!flag) {
            for(int j = pos[0] - k + 1; j <= pos[0] - k + k; j ++)
                cout << s[j];
        }
    }

    return 0;
}

Submission Info

Judge Result