DFA建设克努特莫里斯普拉特算法

Question

我这里指的是克努特莫里斯 - 普拉特（KMP）算法在塞奇威克的书“算法”字符串搜索的轮廓（第四版）。

的KMP算法使用基于确定性有限自动机（DFA）中字符串搜索备份。据我所知，DFA是如何进入的算法，但我不明白如何构建的 DFA，这是由下面的代码片段完成：

dfa[pat.charAt(0)][0] = 1; 
for (int X = 0; j = 1; j< M; j++) { 
    for (int c = 0; c < R; c++) { 
     dfa[c][j] = dfa[c][X]; 
    } 
    dfa[pat.charAt(j)][j] = j+1; 
    X = dfa[pat.charAt(j)][X]; 
} 

其中M是模式的长度pat和R字母表的大小。 charAt()函数返回相应位置上字符的整数值。

有人可以用什么方式这段代码构造一个DFA解释一下吗？我迷失在内循环的实际直观意义中。

Answer 1

让我们来看看下面的足总模式ACACAGA。

上面图代表图案ACACAGA的图形和表格表示。

在此，在DFA状态的数量为M + 1，其中M是该图案的长度。构造DFA的主要内容是从当前状态为每个可能的字符获取下一个状态。给定一个字符x和一个状态k，我们可以通过考虑字符串“pat [0..k-1] x”来得到下一个状态，它基本上是模式字符pat [0]，pat 1 ... pat [k- 1]和字符x。这个想法是获得给定模式的最长前缀的长度，使得该前缀也是“pat [0..k-1] x”的后缀（LPS）。长度值给我们下一个状态。

例如，让我们来看看如何从上面的图中的当前状态，5和字符“C”得到下一个状态。我们需要考虑字符串“pat [0..5] C”，它是“ACACAC”。模式的最长前缀的长度使得前缀是“ACACAC”的后缀是4（“ACAC”）。因此，字符'C'的下一个状态（来自状态5）为4。

// dfa[i][j] = k denotes the transition function will go k'th state 
// with character i from state j 

// DFA will go always (i + 1)'th state from i'th state 
//if the character c is equal to current character of pattern 
dfa[pat.charAt(0)][0] = 1; 

// here X is initialized with LPS (longest prefix suffix) 
// of pattern[0....j - 1]. LPS[0] is always 0 
for (int X = 0; j = 1; j< M; j++) { 
    for (int c = 0; c < R; c++) { // for all possible characters 
     // transition function from j'th state taking character c 
     // will go to the same state where it went from X(LPS)'th state 
     // taking character c (justify it with an example) 
     dfa[c][j] = dfa[c][X]; 
    } 
    // DFA will go always (i + 1)th state from i'th state if 
    // the character c is equal to current character of pattern 
    dfa[pat.charAt(j)][j] = j + 1; 
    X = dfa[pat.charAt(j)][X]; // update LPS 
}