Harjutused 6

1. Tee sufiksipuu sringile 'abracadabra'

2. Vaata "Fast String Searching With Suffix Trees by Mark Nelson Dr. Dobb's Journal, August, 1996" (vaata siit). Proovi teha läbi sufiksi-trie konstruktsioon näidates ära sufiksilingid stringile 'abracadabra'.

3. Loe artiklit Robert Giegerich, Stefan Kurtz, Jens Stoye: Efficient Implementation of Lazy Suffix Trees. (1999). Kirjuta "Executive summary" selle meetodi efektiivusele antud hinnangute kohta (aeg ja maht). (~ 1/2 lehekülge)

4. Tee sufiksitabel stringile 'daansingut tegema ka dansingut, dantsingut tegema'. (vihje - tee programmike ja kasuta sort funktsiooni).

5. Näita kuidas leida kahendotsimisega kõik 'an' esinemised eelmise ülesande sufiksitabelist.

   ---

6. Boonusküsimus (2p): Võta ette loengu sufiksitabelist otsimise algoritm. Kontrolli seal indeksite korrektsust ja esita veavaba täielik versioon. Eesmärk on parandada loengukonspekti esitust, seega peab tulem olema lühike ja täpne. (See, kelle versioon läheb loengukonspekti, saab lisaboonust kuni 2p).

7. Boonusküsimus (4p): Defineeri täpselt LCP tabel sufiksitabelist kahendotsimise kiirendamiseks. Tee ülesande 4 lahendusele vastav LCP tabel mis lubab kiiremaid päringuid. Infot saab Manberi/Myersi artiklist ja Gusfieldi raamatust kui vaja. Tõenäoliselt ka Internetist. Esita üks näide (kus sellest ka kasu oleks). Töö tuleb esitada kirjalikult vormistatult (1-2 lk).