1896 - K Sir

Cerinţa

Fie S un șir de caractere cu litere mici și litere mari. Se sortează în ordine lexicografică toate subsecvențele distincte ale lui S. Se dă un număr K și un vector k cu K numere întregi, se cere pentru fiecare număr cel de ki -lea subșir lexicografic.

Date de intrare

Fișierul de intrare ksir.in conține pe prima linie un șir S, pe a doua linie un număr K, iar pe următoarea linie K numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire ksir.out va conține cele K șiruri de caractere, câte unul pe fiecare linie.

Restricţii şi precizări

• |S| ≤ 200000
• suma |ki | ≤ 200000

Exemplul 1

ksir.in

 FORR
 6
 1 1 2 3 4 5

ksir.out

 F
 F
 FO
 FOR
 FORR
 O

Explicație

Subsecvențele pentru FORR sunt {'F', 'FO', 'FOR', 'FORR', 'O', 'OR', 'ORR', 'R', 'RR'}.

Rezolvare

<syntaxhighlight lang="python" line> def generate_subsequences(s):

   subsequences = set()
   n = len(s)
   for i in range(n):
       for j in range(i+1, n+1):
           subsequences.add(s[i:j])
   return sorted(subsequences)

def main():

   with open("ksir.in", "r") as fin:
       s = fin.readline().strip()
       K = int(fin.readline().strip())
       k_values = list(map(int, fin.readline().split()))

   subsequences = generate_subsequences(s)

   with open("ksir.out", "w") as fout:
       for k in k_values:
           fout.write(subsequences[k - 1] + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>