Tânărul Wesley Crusher, la cererea căpitanului Jean-Luc Picard, a fost transferat temporar într-un centru de radiotelescopie al institutului de fizică de pe stația orbitală Omicron. Recent, aici s-au înregistrat câteva semnale ciudate de natură pulsatoare sosite din centrul galaxiei noastre. Se pune problema dacă aceste semnale reprezintă o pulsație obișnuită a unor stele mari, prezența unor pitice albe sau a unor găuri negre.
Ajutați-l pe Wesley să stabilească adevărul privind aceste semnale și găsiți o modalitate de a analiza mostrele de biți din fișierele înregristrate de stația orbitală Omicron. Wesley își propune să depisteze mostre având lungimi cuprinse între a și b inclusiv, care se pot repeta în fișierul înregistrat. Șirul de biți (fișierul) este de lungime oarecare (maxim 32000). Pentru moment, el nu are nevoie de interpretarea rezultatelor așa că ne face munca mai ușoară.
Cerință
Wesley ne definește pentru un șir x de biți, de lungime n, o secvență de lungime p ca fiind: x[i], x[i+1],…,x[i+p-1] unde i=0 : n-p. El ne cere ca pentru toate secvențele distincte de lungime p (cu a<=p<=b, 2<=a,b<=12) să determinăm numărul de apariții ale acestora. Deoarece semnalele din spațiul cosmic sunt de fapt o suprapunere de diverse semnale, secvențele căutate pot fi suprapuse. Pentru ai fi ușor să citească rezultatele, afișarea secvențelor se va face în ordinea descrescătoare a numărului de apariții, secvențele cu același număr de apariții fiind scrise pe același rând, separate între ele prin virgule. Se afișează secvențele având cel puțin două apariții (secvențele cu o apariție se consideră semnale aleatoare din spațiul cosmic și nu vor fi luate în considerare).
Structura datelor de intrare și de ieșire
Datele de intrare, citite din fișierul text “secv.txt”, unde au fost scrise de senzorii de detecție, sunt:
pe prima linie: a b (separate printr-un spațiu) pe linia doua: șirul de biți (numai 0 și 1)
Exemplu
Intrare
2 4 010100100100010001111011000010100110011110000100100111100100000000
Ieșire
24 secvențe de 00 15 secvențe de 01,10 12 secvențe de 100,000 11 secvențe de 11,001 10 secvențe de 010 8 secvențe de 0100 7 secvențe de 1001,0010,0000 6 secvențe de 111 5 secvențe de 011,110,1000 4 secvențe de 0001,0011,1100 3 secvențe de 101,0111,1111,1110 2 secvențe de 0101,1010,0110
Precizări generale
- Problema constă în compararea tuturor secvențelor (sa le numim s1 și s2), având aceeași lungime p (a <= p <= b). Două secvențe egale cresc un contor de apariții.
- După compararea unei secvențe s1 cu toate secvențele s2 posibile se memorează secvența s1 și numărul ei de apariții (daca secvența nu a mai fost considerată și numărul de aparitii este > 1). Memorarea se face pentru a evita să mai considerăm ulterior aceeași secvență.
- Memorarea secvențelor se face într-un tablou de pointeri la șiruri de caractere, iar numerele aparițiilor asociate secvențelor într-un tablou de întregi.
- Secvențele astfel memorate se sortează descrescator după numărul de apariții.
- Secvențele având același număr de apariții se comasează într-un singur șir de caractere, separându-se între ele prin virgule.
- Se recomandă definirea a două funcții: pentru sortarea unui tablou de secvențe în ordinea descrescătoare a numărului de apariții și pentru a stabili dacă o secvență se află sau nu într-un tablou de secvențe.
- NU se vor folosi bibliotecile: ctype.h, conio.h .
Autor: Florin Pop
Data:07.12. 2010