软考复习之KMP算法
# KMP算法
KMP算法我曾今写过一篇[博客](https://blog.csdn.net/Charlesix59/article/details/119875803)讲过，但是我当时觉得这个算法好烂，就没细讲，后来发现他们还挺喜欢考这个算法的，于是我再开帖讲一下
## 自然语言描述
自然语言描述是我根据《algorithm》的内容以及我自己的理解写出来的，，一般来说是正确的计算next[]与解释KMP的算法，这个方法比较考验悟性，但是原理确实是这样😂
## 考研教材解释
我们还是拿`pat=abcac`举例子，我们从a开始取字串，然后找前缀与后缀的最长相等长度
- ”a“最长相等长度为0
- "ab"最长相等长度0
- "abc"最长相等长度0
- "abca"最长相等长度1
- "abcac"最长相等长度0
所以我们可以得到PM={0,0,0,1,0}
但是我们有公式`右移位数=已匹配的字符数-对应的部分匹配值`
然后 <mark>对应的部分匹配值 是 j 前一个值</mark>，于是为了方便我们把PM整体右移一位，并用-1作为next[0]的值，得到`next[]={-1,0,0,0,1}`
所以我们有公式：
`Move=(j-1)-next[j]`
这就相当于我们将J回退到：
`j回退到的位置=j-Move=j-((j-1)-next[j])=next[j]+1`
所以我们就可以都得到next[]的新的形式：
`next[]={0,1,1,1,2}`
<mark>这里next[]的含义是在j处匹配失败后，j回退到的位置</mark>
## 拓展：更底层的匹配方法
实际上，KMP算法应该生成一个有限状态自动机（DFA），然后通过DFA去匹配字串
继续按照`pat=abcac`为例，画出的DFA如下：
生成DFA的算法如下
```cpp
/*KMP字符串查找*/
class KMP
{
private:
std::string pat;
const static int r = 256;
int *dfa[r]; //建立一个二维数组
public:
KMP(std::string pat)
{
this->pat = pat;
int m = pat.length();
for (int i = 0; i < r; i++)
{
dfa[i] = new int[m];
std::fill(dfa[i], dfa[i] + m, 0);
}
dfa[pat[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[j]][j] = j + 1; //设置匹配成功情况下的值
x = dfa[pat[j]][x]; //更新重启状态
}
}
int seatch(std::string txt)
{
int i, j, n = txt.length(), m = pat.length();
for (i = 0, j = 0; i < n&&j < m; i++)
{
j = dfa[txt[i]][j];
}
if (j == m)
return i - m; //找到匹配
else
return n; //未找到匹配
}
};
```