KMP算法

失效函数f(i)

假如目标串是Sub,则失效函数f(i)表示既是Sub(0,i)的真前缀又是Sub(0,i)的后缀的最长串的长度,通俗地说就是前后相等的子串长度。

有时候也被叫做next数组，因为它代表了如果匹配失败下一次将从哪个开始匹配

举一个书本中的例子，求ababaa的失效函数。

失效函数自变量	子串	首尾相等的子串	失效函数值
0	a		0
1	ab		0
2	aba	a	1
3	abab	ab	2
4	ababa	aba	3
5	ababaa	a	1

当使用编程语言实现时，求值思想是在上一个失效函数值的基础上求出当前所求的失效值。这个是我从编译原理第二版上看到的方法，比较简洁明了。继续使用上面的例子，对ababaa求失效函数，根据定义我们可以直接得出f(0) 为0。

在求其他位置的效值的过程中，我们维护两个下标：一个是当前位置的下标，一个上一个位置的失效值。

为什么要保存这两个下标呢？

1.我们通过当前位置下标取得要比较的字符，并将失效值写入对应的地方。

2.通过观察可以发现，假如上一个位置的失效函数值为i，当前位置为j，那么在i和j之前的字符都已经被对比且为相等了，如果i和j对比不相等，直接把i变成i-1处的失效函数值，假设是q，那么q和j之前的字符也肯定是比对且为相等的了，这就是失效函数的神奇之处。

文字描述不容易理解，下面通过画图来描述

image

用c++实现


vector<int> next(const string & S )
{
    vector<int> f(S.length());  //已经知道需要求的值的个数
    int i = 0;
    f[0]= 0; //第一个肯定是0
    for (int j = 1; j < S.length(); j++) {
        while (i > 0 & S[i] != S[j]) i = f[i-1];  //如果当前要对比的字符还是不相等且没回退到第一个则一直回退到前一个的失效函数值处
        if (S[i] == S[j]) {
            ++ i;
            f[j] = i;
        }else {
            f[j]= 0;
        }
    }
    return f;
}

使用求得的失效函数

使用KMP算法求子串位置，查找到则返回-1.
在前面的求失效函数的过程中我们已经利用了失效函数了，如果没理解可以多看几遍，这个地方有点绕。原理是当对比到第j个字符发现不相等时，前面的j-1个字符其实已经是相等的了，接下来要做的就是利用这一部分信息来避免回溯。

对比发现不相等的情况以及处理

书中使用的术语是“滑动”，效果如图

根据上一位置失效值移动

将上述思想使用c++表达，未做错误处理，因为这篇文章的目的是理清思路。

int index (const string & S,const string &B)
{
    vector<int> f = next(B);
    int i = 0;
    for (int j = 0; j < S.length(); j++) {
            while (i > 0 && B[i] != S[j]) i = f[i-1];
            if (S[j] == B[i]) 
            if (j == B.length()) return j;
    }   
    return -1;

}