Algoritmul cerea deci sa se afle daca un sir este secventa intr-un alt
sir. Trebuie sa incep cu comentariu ca timpul de executie a fost dat cam
mare, fiind necesare doar 0.5-1 sec./test. Oricum am corectat cu 5 sec./test.
    Cea mai buna sursa fost cea a lui Musaloiu Razvan din 3 motive:
      1.A luat punctaj maxim -> conditie evidenta
      2.A fost singurul program care a mers instantaneu pe toate testele
      3.A ales algoritmul Boyer Moore pentru rezolvare
    O sa discut un pic despre punctul 3. In primul rand celelalte surse ce
au obtinut punctaj maxim au fost:
    - cele ale lui Dumitrascu Irina si Drula Catalin ce au folosit
      algoritmul KMP
    - cele ale lui Dumitru Bogdan si Bogdan Stroe ce au folosit un algoritm
      patratic, dar foarte mult optimizat

    Despre ultimele 2 surse, nu fac prea multe comentarii, dar consider
ca pe anumite teste puteau "pica".
    Acum o sa justific de ce pentru aceasta problema, algoritmul Boyer-Moore
era mai indicat decat algoritmul KMP. (pentru cei ce nu cunosc acesti doi
algoritmi, le recomand "Gazeta de Informatica" Nr. 2/1998, articolul lui
Cosmin Truta - pt. Boyer-Moore, si cartea "Provocarea Algoritmilor" de
Victor Mitrana - pt. KMP. De asemenea puteti solicita ca cei ce au obtinut
punctaje maxime sa posteze pe lista descrierea acestor algoritmi. De altfel,
ii rog chiar eu pe respectivii sa faca acest lucru - deh, punctajul maxim
are si el un pret :-) ).
    Algoritmul Boyer-Moore este aplicabil pentru un set de simboluri aflat
intr-o multime finita, si relativ de cardinal redus, deoarece el pastreaza
ca unica structura auxiliara un vector avand un numar de elemente egal
cu cardinalul multimii respective. Astfel, pentru problema de fata, era
necesara folosirea unui vector de doar 255 de elemente de tip intreg !!!
(array[#0..#255] of integer).
    Algoritmul KMP in schimb pastreaza ca structura auxiliara un vector
avand un numar de elemente egal cu numarul de elemente din sirul de cautat.
Aici de exemplu trebuia sa retineti un vector de 25000 de elemente intregi,
de aproximativ 100 de ori mai multa memorie decat pt. Boyer-Moore. Chiar mai
mult, in caz ca limita fisierelor era de cativa mega (nu am dat astfel de
limite atat pentru a nu creea teste super-gigantice, cat si pentru a se putea
totusi aplica KMP), folosirea acestui algoritm era aproape imposibila. In
schimb, in cazul algoritmului Boyer-Moore, indiferent cat de mari ar fi
fisierele, el foloseste tot 500 de bytes de memorie !!!
    Va dati seama ca in acest caz, algoritmul Boyer-Moore este de nenumarate
ori mai bun decat KMP-ul. Totusi nu trebuie subestimata nici eficienta acestui
algoritm. Exista cazuri in care KMP-ul este de nenumarate ori mai bun decat
Boyer-Moore-ul. Spre exemplu, sa consideram o problema ce cere sa afle
daca un sir de numere A apare intr-un alt sir de numere B. Sa presupunem
ca numerele sunt intre 1 si 10.000.000, iar lungimile celor doua siruri
sunt maxim 10000. In acest caz KMP-ul tine un vector de doar 10000 de
elemente, in timp ce Boyer-Moore-lui i-ar trebui un vector de 10.000.000
de elemente !!!
    Concluzia este ca, in functie de datele problemei, trebuie sa alegeti
algoritmul optim de rezolvare.
    Daca mai cunoasteti un alt algoritm eficient de rezolvare in afara de
cei doi discutati mai sus, va rog mult sa imi scrieti.