具有有限自动机的字符串匹配 [英] string matching with finite automata

问题描述

我正在科门(Cormen)的书算法简介"中阅读有关字符串算法的内容.对于过渡，如下所示.

I am reading about string algorithms in Cormen's book "Introduction to Algorithms". For Transition which is shown below.

我的问题:为什么我们要做min(m+1, q+2)，为什么我们要使m分别增加1和q2.

My question: why are we doing min(m+1, q+2) and why are we incrementing m by 1 and q by 2.

以下链接对上述问题有帮助.

Following link has back ground to above question.

http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Fall2009/StringMatching.pdf

请在此处提供一个简单的示例.

Kindly help here with a simple example.

Algorithm Compute-Transition-Function(P, Sigma)
m = length(P);
for  q = 0 through m  do
   for each character  x  in Sigma
       k = min(m+1, q+2);
       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.

推荐答案

• 它是m + 1，因为在下一个repeat循环中，k首先减小.
• 它是q + 2，因为在repeat中，您先从q + 1开始，所以至少要有1个字符.

  ---

• It is m + 1 because in the next repeat loop k is decreased first.
• It is q + 2 because in the repeat you start then with q + 1 so have at least 1 char.

  ---

以下代码可能存在边界问题(q == m缺失)， 但想使索引更清晰.

The following code might have a boundary problem (q == m is missing), but wants to make the indexing a bit clearer.

m = length(P);
for  q = 0 through m - 1 do // Loop through substrings [0, q+1]
   for each character  x  in Sigma
       k = q+1;
       // work backwards from q+1
       while not Pk 'is-suffix-of' Pqx;
       do k = k-1; end do;
       d(q, x) = k; // assign transition table
   end for;
end for;

return  d;

这篇关于具有有限自动机的字符串匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！