Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Rabin-Karp

Umožňuje vyhľadávanie viacerých reťazcov v texte naraz - užitočné napr. na hľadanie plagiátov. Základnou myšlienkou je vyhľadávanie v texte pomocou hashov (rolling hashes - idea je `s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]`)...

Algoritmus pre vyhľadávanie jedného reťazca:

    1 function RabinKarp(string s[1..n], string sub[1..m])
    2     hsub := hash(sub[1..m])
    3     hs := hash(s[1..m])
    4     for i from 1 to n-m+1
    5         if hs = hsub
    6             if s[i..i+m-1] = sub
    7                 return i
    8         hs := hash(s[i+1..i+m])
    9     return not found

Najhoršia zložitosť je . Pri vyhľadávaní viacerých reťazcov len spočítame hashe všekých hľadaných stringov a pri nájdení niektorého z hashov príslušný reťazec porovnáme s textom... Ostatné algoritmy spotrebujú čas na nájdenie 1 reťazca a teda na vyhľadanie reťazcov. Naproti tomu tento algoritmus má očakávanú zložitosť - pretože vyhľadávanie v hashovacej tabuľke, či je hash podreťazca textu rovný hashu niektorého z hľadaného reťazcov, trvá .