Soluție HackerRank pentru Ashton and String. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Ashton and String

Cerinta completa

Ashton appeared for a job interview and is asked the following question. Arrange all the distinct substrings of a given string in lexicographical order and concatenate them. Print the [Expresie matematică indisponibilă în copia arhivată] character of the concatenated string. It is assured that given value of [Expresie matematică indisponibilă în copia arhivată] will be valid i.e. there will be a [Expresie matematică indisponibilă în copia arhivată] character. Can you help Ashton out with this?

For example, given the string [Expresie matematică indisponibilă în copia arhivată], its distinct substrings are [Expresie matematică indisponibilă în copia arhivată]. Sorted and concatenated, they make the string [Expresie matematică indisponibilă în copia arhivată]. If [Expresie matematică indisponibilă în copia arhivată] then, the answer is [Expresie matematică indisponibilă în copia arhivată], the [Expresie matematică indisponibilă în copia arhivată] character of the 1-indexed concatenated string.

Note We have distinct substrings here, i.e. if string is aa, it’s distinct substrings are a and aa.

Function Description

Complete the ashtonString function in the editor below. It should return the [Expresie matematică indisponibilă în copia arhivată] character from the concatenated string, 1-based indexing.

ashtonString has the following parameters:
– s: a string
– k: an integer

Input Format

The first line will contain an integer [Expresie matematică indisponibilă în copia arhivată], the number of test cases.

Each of the subsequent [Expresie matematică indisponibilă în copia arhivată] pairs of lines is as follows:
– The first line of each test case contains a string, [Expresie matematică indisponibilă în copia arhivată].
– The second line contains an integer, [Expresie matematică indisponibilă în copia arhivată].

Constraints

[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
Each character of string [Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată] will be an appropriate integer.

Output Format

Print the [Expresie matematică indisponibilă în copia arhivată] character (1-based index) of the concatenation of the ordered distinct substrings of [Expresie matematică indisponibilă în copia arhivată].

Sample Input

1
dbac
3

Sample Output

c

Explanation

The substrings when arranged in lexicographic order are as follows 

a, ac, b, ba, bac, c, d, db, dba, dbac

On concatenating them, we get 

aacbbabaccddbdbadbac

The third character in this string is c.

Limbajul de programare folosit: cpp20

Cod:

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

vector<int> buildSuffixArray(const string &s) {
    int n = (int)s.size();
    vector<int> sa(n), rnk(n), tmp(n);

    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rnk[i] = (unsigned char)s[i];
    }

    for (int k = 1;; k <<= 1) {
        auto cmp = [&](int i, int j) {
            if (rnk[i] != rnk[j]) return rnk[i] < rnk[j];
            int ri = (i + k < n) ? rnk[i + k] : -1;
            int rj = (j + k < n) ? rnk[j + k] : -1;
            return ri < rj;
        };

        sort(sa.begin(), sa.end(), cmp);

        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i < n; i++) rnk[i] = tmp[i];

        if (rnk[sa[n - 1]] == n - 1) break;
    }

    return sa;
}

vector<int> buildLCP(const string &s, const vector<int> &sa) {
    int n = (int)s.size();
    vector<int> rank(n), lcp(n, 0);

    for (int i = 0; i < n; i++) rank[sa[i]] = i;

    int h = 0;
    for (int i = 0; i < n; i++) {
        int r = rank[i];
        if (r == 0) continue;

        int j = sa[r - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[r] = h;
        if (h > 0) h--;
    }

    return lcp;
}

long long tri(long long x) {
    return x * (x + 1) / 2;
}

char solveOne(const string &s, long long k) {
    auto sa = buildSuffixArray(s);
    auto lcp = buildLCP(s, sa);
    int n = (int)s.size();

    for (int i = 0; i < n; i++) {
        long long len = n - sa[i];
        long long common = lcp[i];
        long long blockChars = tri(len) - tri(common);

        if (k > blockChars) {
            k -= blockChars;
            continue;
        }

        long long lo = common + 1;
        long long hi = len;
        while (lo < hi) {
            long long mid = (lo + hi) / 2;
            long long pref = tri(mid) - tri(common);
            if (pref >= k) hi = mid;
            else lo = mid + 1;
        }

        long long lengthPicked = lo;
        long long charsBefore = tri(lengthPicked - 1) - tri(common);
        long long pos = k - charsBefore;
        return s[sa[i] + pos - 1];
    }

    return '?';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        string s;
        long long k;
        cin >> s >> k;
        cout << solveOne(s, k) << '\n';
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464637895

Link challenge: https://www.hackerrank.com/challenges/ashton-and-string/problem

Ashton and String