4

π 前置関数を使用して、時間 O(m |Σ|) で文字列一致オートマトンの遷移関数 δ を計算するための効率的なアルゴリズムをどのように与えることができますか?

有限オートマトンで遷移関数を計算したい。通常の遷移関数の複雑さは O(m^3|Σ|) です。ここで、m = パターン P の長さ、Σ はアルファベットです。COMPUTE_TRANSITION_FUNCTION(P,Σ)

m = length(P);
for  q = 0 through m  do
    for each character  x  in Σ
    k = min(m+1, q+2); // +1 for x, +2 for subsequent repeat loop to decrement
        repeat  k = k-1 // work backwards from q+1
        until  Pk 'is-suffix-of' Pqx;
        d(q, x) = k;    // assign transition table
end for; end for;

return  d;
End algorithm.

π は KMP アルゴリズムで定義された接頭関数です。

4

2 に答える 2

2

O(m.|Σ|) アルゴリズムがあり、トランザクション関数には O(m.|Σ|) 可能な入力があるため、時間の複雑さのためにこれより優れたアルゴリズムはありません。

π を計算したと仮定し、d(q, x) を計算したいとします。d(q, x) は、現在状態 q にあり、入力の現在の文字が x である場合、どの状態に進むべきかを意味します。現在の文字が P[q] の場合、q+1 文字が一致するため、状態 q + 1 に移動する必要があります。したがって、d(q, p[i]) = q + 1 です。それ以外の場合は、数値が小さい状態に移動する必要があります。π[q] は、P[0 .. π[q]] が P[0 .. q] のサフィックスである q の前の最後の状態を意味します。そのため、以前に設定した文字 p[i] を除いて、状態 π[q] の出力を状態 q の出力にコピーします。

ご理解いただければ幸いです。

于 2012-05-04T13:35:00.237 に答える
0

O（m ^ 2 | E |）かかる答えが得られました。また、テーマに関する質問 32.4-8 があります。

ここにあります：

vector<vector<size_t>> Preprocess(const string &_pattern)
{
    vector<string> pattern_vec;
    for (size_t i = 0; i <= _pattern.size(); ++i)                                         // m
        pattern_vec.push_back(_pattern.substr(0, i));

    vector<vector<int>> is_match_matrix(1 + _pattern.size(), vector<int>(1 + _pattern.size(), -1));
    for (size_t i = 0; i < is_match_matrix.size(); ++i)                                            // m
    {
        for (size_t j = 0; j <= i; ++j)                                                      // m
        {
            if (pattern_vec[i - j] == _pattern.substr(j, i - j))
            {
                is_match_matrix[i][j] = i - j;
            }
        }
    }

    // note:
    is_match_matrix[_pattern.size()][0] = -1;

    vector<vector<size_t>> status_matrix(1 + _pattern.size(), vector<size_t>(26, 0));

    for (size_t i = 0; i < status_matrix.size(); ++i)                                            // m
    {
        char c = 'a';
        while (c <= 'z')                                                                         // E
        {
            for (size_t j = 0; j <= i; ++j)                                                      // m
            {
                if (-1 != is_match_matrix[i][j] && c == _pattern[is_match_matrix[i][j]])
                {
                    status_matrix[i][c - 'a'] = is_match_matrix[i][j] + 1;
                    break;
                }
            }

            c++;
        }
    }

    return status_matrix;
}
于 2014-09-25T06:34:27.933 に答える