Cvičenia: 8. týždeň

Ciele cvičení:

  • rozumieť a vedieť implementovať KMP algoritmus
  • vedieť, ako možno hašovanie využiť pri stringologických algoritmoch

Hľadanie výskytu intuitívne

Implementujte naivný algoritmus na nájdenie všetkých výskytov vzorky v reťazci. Využitie pritom schému:

public static void najdiVyskyty(String retazec, String vzorka) {
        int poz = 0;
        while (poz <= retazec.length() - vzorka.length()) {
                int i = 0;
                while (vzorka.charAt(i) == retazec.charAt(poz + i)) {
                        //...
                }

                //...
        }
}
[$[Get Code]]
  • Je pravdou, že každý "zaujímavý" okamih výpočtu možno charakterizovať obsahom premenných poz a i?

Prefixový sufix

Naprogramujte (bez ohľadu na efektívnosť implementácie) metódu, ktorá pre zadaný reťazec nájde najdlhší prefix zadaného reťazca, ktorý je zároveň jeho sufixom.

public static int prefixovySufix(String s) {

}
[$[Get Code]]

Hľadanie výskytu intuitívne - simulácia

Uvažujme reťazec bacbabababacaab. Demonštrujte, ako by prebiehal naivný algoritmus so vzorkou ababaca.

  • Nech je vzorka zarovnaná na 5. znak reťazca. Vo chvíli, keď nastane "nezhoda" c vs. a, ako by ste vedeli využiť to, že už máte 4 znaky vzorky úspešne "zamatchované" s reťazcom? Je treba spraviť poz++ a i=0 alebo ide premenné poz a i zmeniť tak, aby sme elimovali nejaké (ideálne, čo najviac) zbytočné kroky.

KMP

  • S využitím simulátora lemmingov (http://ics.upjs.sk/~mikes/var/lemming/) pre zadaný reťazec a vzorku (napr. z predošlej úlohy) pre každú pozíciu "spadnutia lemminga" určte pozíciu, na ktorej sa nachádza najbližší nerozbitý lemming naľavo od neho.
  • Rozdiskutujte význam "failure" tabuľky v KMP algoritme. Navrhnite, ako ich možno "konštruovať" (aj neefektívne) s využitím metódy na prefixový sufix.
  • Implementujte KMP algoritmus.
  • Rozdiskutujte možnosti efektívnej implementácie "failure" tabuliek KMP algoritmu.

Hašovanie

  • Pripomeňte si, čo je to hašovanie a ako sa využíva v triedajch JCF (napr. HashSet). Na čo slúžia metódy equals a hashCode.
  • Navrhnite a implementujte nejaký vlastný jednoduchý spôsob na výpočet hashu zadaného reťazca.
  • Navrhnite a implementujte nejaký vlastný jednoduchý spôsob na výpočet hashu zadaného reťazca tak, aby ste dokázali z hashu reťazca efektívne vypočítať hash reťazca, ktorý vznikne odobraním prvého znaku reťazca alebo pridaním nového znaku na koniec reťazca.

Hašovanie a vyhľadávanie podreťazcov

Rozdiskutujte a implementujte algoritmus na nájdenie všetkých výskytov zadanej vzorky v reťazci, ktorý by využíval hašovanie.