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ů

### Knuth-Morris-Pratt

Obdoba Aho-Corasick, ale hľadá len jedno slovo. Samozrejme nie je potrebná dopredná funkcia (vždy iba nasledujúci znak), používa sa partial match tabuľka (failure funkcia).

    algorithm kmp_search:
    input:
    S (the text to be searched)
    W (the word sought)

    m = 0 (the beginning of the current match in S)
    i = 0 (the position of the current character in W)
    an array of integers, T (the table, computed elsewhere)

    while m + i is less than the length of S, do:
    if W[i] = S[m + i],
    i = i + 1
    if i equals the length of W,
    return m
    otherwise,
    m = m + i - T[i],
    if i is greater than 0,
    i = T[i]

    (if we reach here, we have searched all of S unsuccessfully)
    return the length of S

Zložitosť algoritmu je je (k je dĺžka S) - cyklus je vykonaný najviac krát.

Algoritmus na výrobu tabuľky:

    algorithm kmp_table:
    input:
    W (the word to be analyzed)
    T (the table to be filled)

    i = 2 (the current position we are computing in T)
    j = 0 (the zero-based index in W of the next
    character of the current candidate substring)

    (the first few values are fixed but different
    from what the algorithm might suggest)
    let T[0] = -1
    T[1] = 0

    while i is less than the length of W, do:
    (first case: the substring continues)
    if W[i - 1] = W[j],
    T[i] = j + 1
    i = i + 1
    j = j + 1

    (second case: it doesn't, but we can fall back)
    otherwise, if j > 0,
    j = T[j]

    (third case: we have run out of candidates. Note j = 0)
    otherwise,
    T[i] = 0
    i = i + 1

Zložitosť tohoto algoritmu je (n je dĺžka W) - cyklus skončí najviac po iteráciách.