Termenul anterior dintr-un șir de cuvinte

Observația pe care se sprijină rezolvarea

Regula de formare este sₙ = sₙ₋₁sₙ₋₂: termenul de rang n se obține scriind termenul dinaintea lui și lipind după el pe cel de dinaintea acestuia. De aici rezultă că termenul anterior este chiar începutul termenului dat.

Pentru x = DA:

Termenul de rang 5 începe cu DA*DADA*, adică exact cu termenul de rang 4. Prin urmare, ca să obținem termenul căutat, nu avem nevoie să-l construim: este de ajuns să știm câte caractere are și să afișăm atâtea caractere de la începutul șirului citit de pe a treia linie a fișierului.

Rămâne o singură întrebare: câte caractere are termenul anterior? Lungimile termenilor se pot calcula fără a construi termenii înșiși. Notând cu lg₁, lg₂, … lungimile lor:

• lg₁ este numărul de litere ale cuvântului x, deci 1 sau 2;
• lg₂ = lg₁ + 1, fiindcă s₂ este x urmat de un singur asterisc;
• lgᵢ = lgᵢ₋₁ + lgᵢ₋₂ pentru i > 2, fiindcă termenul este concatenarea celor doi dinaintea lui.

Pentru x = DA se obține șirul de lungimi 2, 3, 5, 8, 13, 21, … — un șir de tip Fibonacci.

Descrierea metodei de rezolvare

Se citesc din fișier cuvântul x și numărul n. Se calculează lungimea primului termen, ca număr de litere ale lui x, și lungimea celui de-al doilea, cu unu mai mare.

Se generează apoi, unul câte unul, termenii șirului de lungimi, fiecare ca sumă a celor doi dinaintea lui. Nu se rețin toate valorile, ci numai ultimele două: lungimea curentă și cea dinaintea ei. Generarea se oprește în momentul în care lungimea curentă devine egală cu n, adică s-a ajuns la termenul dat în fișier. În acel moment, valoarea reținută ca lungime anterioară este chiar numărul de caractere ale termenului căutat.

Se citește apoi a treia linie a fișierului și se afișează primele atâtea caractere câte indică această valoare. Nici aici nu este nevoie ca întreaga linie să fie păstrată în memorie: caracterele se citesc unul câte unul și se scriu pe ecran pe măsură ce sunt citite, iar citirea se oprește după ce s-au afișat toate caracterele cerute.

Justificarea eficienței

Din punctul de vedere al timpului. Lungimile termenilor cresc după regula lui Fibonacci, deci cresc exponențial. Pentru a ajunge la o valoare de ordinul 10⁶ sunt de ajuns aproximativ 30 de adunări, indiferent de datele de intrare. Restul lucrului este citirea și afișarea caracterelor termenului căutat, care se face într-o singură parcurgere, fără reveniri. Timpul de executare este deci liniar în raport cu lungimea datelor citite, adică O(n) — și nu se poate mai bine, fiindcă rezultatul însuși are, în cazul cel mai defavorabil, lungime comparabilă cu n.

Din punctul de vedere al memoriei. Nu se memorează niciun termen al șirului s și nici linia citită din fișier. Se rețin doar cuvântul x, numărul n, două lungimi și caracterul curent — un număr de variabile care nu depinde de n. Memoria suplimentară folosită este deci constantă, O(1).

O soluție care ar construi efectiv termenii, prin concatenări succesive, ar trebui să păstreze în memorie șiruri de până la 10⁶ caractere și ar face un număr de copieri proporțional cu lungimea lor la fiecare pas. Ea ar da rezultatul corect, dar cu un consum de memorie și de timp mult mai mare, fără niciun câștig.