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] 表示 q 之前的最后一个状态，即 P[0 .. π[q]] 是 P[0 .. q] 的后缀。所以我们将状态 π[q] 的输出复制到状态 q 的输出，除了我们之前设置的字符 p[i]。

我希望你明白！

于 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 回答