Geek asks and answers

Calculate transition function

How can I give an efficient algorithm for calculating the transition function δ for an automaton matching rows in time O (m | Σ |) using the π prefix function?

I want to calculate the transition function in a state machine. The normal transition function has complexity O (m ^ 3 | Σ |), where m = the length of the picture P and Σ is the alphabet. 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.

π is the prefix function defined in the KMP algorithm

+3
source share
2 answers

There is an algorithm O (m. | Σ |), and since the transaction function has a possible input O (m. | Σ |), there is no better algorithm because of the time complexity.

, π, d (q, x). d (q, x) , , q, - x. P [q], q + 1, q + 1. d (q, p [i]) = q + 1. . π [q] q, P [0.. π [q]] P [0.. q]. π [q] q, p [i], .

, !

+1

, 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;
}
0

More articles:


All Articles