KMP的DFA理解对新手来说还是很比较费劲
自动机原理如下图
image.png
我们先说其怎么样利用DFA，然后再实现DFA
public int search(String txt) {
// 再txt上模拟DFA的运行
int m = pat.length();
int n = txt.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == m) return i - m; // 找到匹配，返回匹配字符串的头索引
return n; // 没有找到
}
其中最重要的便是
j = dfa[txt.charAt(i)][j];
表示txt中第 i 个位置的字符往DFA里面输入，如果输入对了，DFA里面的状态 j 会前进一个状态，如果输入错了，DFA里面的状态就会返回到应有的状态。当状态 j 值 = 模式字符串pat的长度时，匹配就成功了。
最重要的便是构建一个DFA；
基本思想是：
1、这里输入的字符是模式pat字符串内的所有的字母，将其设为 ‘行’ 坐标。也就是DFA数组里的 [这里] [ ]
（其实也不是这样，只不过你的字母如果不在pat内的话，他在DFA中的值一定是等于0的）
2、然后将pat所在 j 位置的 ’字符‘ 设为纵坐标（注意字符才是纵坐标，j是状态！），并且在此 j 还有另外一种意义，那就是 “状态”。是DFA中的[ ][ 这里]。
3、所有pat的状态初始状态肯定是1,0,0······· 的
image.png
由于DFA的构建是由PAT字符串自己构建的（见算法导论），所以只用对自己比较即可，大概的意思是
如果要比较的txt字符串为：
TXT为 |A B A B A| B A B A B C ——①
PAT为 |A B A B A| C ——②
在此处我们只要再次用模式字符串pat，比较①②中相同的部分即可
而不用再①中重新从txt.charAt(1)中在开始继续比较，直接通过我们的DFA遍历自己的PAT一次就可以找出下一次应该在哪里开始匹配（或者说状态是多少）。
所以此处PAT自己遍历自己
.|A B A B A| --------------------------------------------（0）
***|A B A B A|不匹配
.|A B A B A|
******|A B A B A|
--------i---i---i有三处匹配
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++)
{
// Compute dfa[][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];//更新重启状态
}
其中比较难理解的便是更新重启状态
X = dfa[pat.charAt(j)][X];//更新重启状态
这个句话可以理解为，pat第 j 个位置的字符输入到DFA中后，产生了怎样的一个状态x？ 然后把这个x当成下一个状态的初始值。
在此处，j是从第二列才开始记录的状态，所以可以这么做。
（有点递推公式的感觉？由已知的第一个情况，将第二个情况带入，得到第二个情况，依此类推？？？？？）
第一列是
image.png
第二列
image.png
j是从第二列开始，所以第一次循环就是X = dfa[pat第二个字母][0]，也就是[b][0]结果是0，此处的情况就是前述（0）情况。此时把其记录xia'lai
网友评论