Tällä viikolla aloitamme tutustumisen merkkijonoalgoritmeihin. KKKK:n luvut 31 ja 32 ovat hyödyllistä luettavaa.

Laskareissakin esitetty rolling hash -visualisaatio on käytettävissä osoitteessa http://www.cs.helsinki.fi/u/totalvit/alon/vis8/hash.html.

Vinkit

Silmukka

[hint]Tässä tehtävässä voi tulla ongelmaksi, että hajautusarvoissa esiintyy törmäyksiä. Yksi hyvä valinta moduloksi on 2^{64}, jolloin erilaisia hajautusarvoja on mahdollisimman paljon. Tämä on myös helppoa toteuttaa, koska koodiin ei tarvitse liittää omaa modulon käsittelyä vaan riittää käyttää 64-bittistä kokonaislukutyyppiä ja antaa sen ylivuotaa.[/hint]

Alijono

[hint]Keksi ahne strategia, jossa muodostetaan Maijan merkkijonoa yksi merkki kerrallaan. Merkkijonohajautuksesta ei todennäköisesti ole apua.[/hint]

Päiväkirja

[hint]Muodosta tulostetta merkki kerrallaan, ylläpitäen hajautusarvoa algoritmin nimen pituiselle loppuosalle. Jos hajautusarvo täsmää algoritmin nimeen, poista täsmäävä loppuosa ja jatka lisäämistä.[/hint]

Salaus

[hint]Käytä hajautusfunktiota, jonka arvo ei muutu, vaikka kirjaimet muutetaan (esim. kun kaikki A-kirjaimet vaihdetaan B-kirjaimiksi ja toisinpäin).[/hint]