전이 함수 계산

Question

π 접두사 함수를 사용하여 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. 

π는 O가

Answer 1

KMP 알고리즘에 정의 된 접두어 함수 (m |. Σ |) 알고리즘 및 거래 기능 O (m을 가지고 있기 때문이다. | Σ |) 가능한 입력, 시간 복잡성으로 인해 더 나은 알고리즘이 없습니다.

π를 계산했다고 가정하고 d (q, x)를 계산하려고합니다. 우리가 현재 상태 q에 있고 입력의 현재 문자가 x라면 d (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]의 출력을 복사합니다.

나는 그것을 이해하시기 바랍니다!

Answer 2

나는 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; 
}