• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Problema seti,Campion 2009

0
  • Publicat de Andrei Avădănei
  • în C/C++ · Probleme algoritmică · Tehnic
  • — 13 nov., 2009 at 7:10 pm

Vasile este convins ca nu suntem singuri in Univers. In fiecare seara el inregistreaza semnale venite din spatiu si le memoreaza sub forma unui sir T format din litere ale alfabetului latin. Pentru a decodifica mesajele primite din spatiu, Vasile utilizeaza un sir auxiliar P asupra caruia efectueaza urmatoarele operatii:
A: adauga un caracter la sfarsitul sirului P
Q: afla de cate ori sirul P apare ca subsecventa a sirului T.
Initial sirul P este vid.

Cerinta

Scrieti un program care, cunoscand mesajul T si operatiile efectuate de Vasile asupra sirului P, afiseaza raspunsul la operatiile de tip Q.

Date de intrare

Fisierul de intrare seti.in contine pe prima linie mesajul T. Pe cea de a doua linie sun descrise operatiile pe care le efectueaza Vasile, sub forma unui sir de caractere. Al i-lea caracter din acest sir este o litera (semnificand faptul ca Vasile adauga litera respectiva la sfarsitul sirului P) sau un ? (semnificand o operatie de tip Q).

Date de iesire

Fisierul de iesire seti.out va contine cate o linie pentru fiecare operatie de tip Q, linie pe care va fi scris raspunsul (de cate ori sirul P apare ca subsecventa a sirului T).

Restrictii

  • Åžirul T contine cel mult 200 000 litere ale alfabetului latin.
  • Vasile executa cel mult 200 000 de operatii.
  • Åžirul P nu incepe cu caracterul ‘?’.

Exemple

seti.in seti.out
mamamamaiasieulaMamaia

ma?ma?i?e?

5

3

1

0

Solutia mea

Aceasta problema este o aplicatie directa a algoritmului de cautare a unui subsir intr-un alt sir,sau algoritmul lui Knuth-Morris-Pratt(KMP) ce va fi prezentat curand si pe blog.Trebuie citit normal sirul A(primul sir), iar in al doilea se vor elimina intrebarile.Construirea prefixului noului sir B se va face clasic.Rezolvarea in sine are loc la modificarea algoritmului de determinare a unui subsir intr-un sir.Cei care cunosc algoritmul KMP stiu ca el determina practic cel mai lung prefix ce l-a gasit pana la un moment dat.Astfel de vom folosi de aceasta informatie si vom avea sol[q]++ (vom adauga un prefix de lungime q la lista celor existente deja).Generarea vectorului de solutii(practic generarea tuturor solutiilor pentru orice prefix de lungime <= m se va face in momentul in care vom adauga sol[i] la sol[pi[i]], pi[i] fiind prefixul sirului B.Urmeaza afisarea rezultatelor in functie de intrebari.Acest algoritm va avea complexitate aproape liniara(N+2M+k), N = strlen(A),M=strlen(B), k = strlen(intrebari).
Descarcati solutia pentru problema seti de la Campion 2009.

Etichete: .campionalgoritmicainformaticaOJIONIProbleme algoritmicăseti

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Cei de la Microsoft anunta ca Windows 7 nu a copiat Mac OS X
  • Articolul următor Problema Bal,Campion 2009

  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • aprilie 2021
    L Ma Mi J V S D
     1234
    567891011
    12131415161718
    19202122232425
    2627282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Problema seti,Campion 2009
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons