2

ウィキペディアでKMP アルゴリズムを読んでいます。「テーブル構築アルゴリズムの擬似コードの説明」セクションに、私を混乱させる1行のコードがあります。let cnd ← T[cnd]

コメント(second case: it doesn't, but we can fall back)があります。それは本当に私を混乱させるからです。

テーブル構築アルゴリズムの完全な疑似コードは次のとおりです。

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
        an array of integers, T (the table to be filled)
    output:
        nothing (but during operation, it populates the table)

    define variables:
        an integer, pos ← 2 (the current position we are computing in T)
        an integer, cnd ← 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 pos < length(W) do
        (first case: the substring continues)
        if W[pos - 1] = W[cnd] then
            let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (second case: it doesn't, but we can fall back)
        else if cnd > 0 then
            let cnd ← T[cnd]

        (third case: we have run out of candidates.  Note cnd = 0)
        else
            let T[pos] ← 0, pos ← pos + 1
4

1 に答える 1

1

の適切な接尾辞でもあるパターンWT[cnd]の以前の最長の適切な接頭辞の長さが含まれているため、にフォールバックできます。したがって、現在の at の文字が at の文字と一致する場合、の適切な接頭辞の最長の長さを延長できます(これが最初のケースです)。W[0...cnd]W[pos-1]W[T[cnd]]W[0...pos-1]

以前に計算された値に依存する動的計画法のようなものだと思います。

この説明が役立つかもしれません。

于 2014-07-01T13:56:30.663 に答える