数据结构——串的模式匹配算法（BF算法和KMP算法）

算法目的：

        确定主串中所含子串（模式串）第一次出现的位置（定位）

算法应用：

        搜索引擎、拼写检查、语言翻译、数据压缩

算法种类：
        BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）又称暴力破解法

        KMP算法（特点：速度快）

BF算法

        BF算法亦称简单匹配法，采用穷举的思路。

算法的思路是从S的每一个字符开始依次与T的字符进行匹配。

 模式串跟主串逐个字符比较，如果第一个字符相同，则i++、j++比较第二个字符，以此类推，当所有字符相同，则匹配成功，如果有一个不同，模式串就从主串的第二个字符开始比较，即

第二轮比较：

又匹配失败，回溯

再次逐个比较

匹配成功，不用再管主串后面的字符了，此时i = 7，j = 5

模式串的位置为i - t.length = 3

Index(S,T,pos)

• 将主串的第pos个字符和模式串的第一个字符比较，
• 若相等，继续逐个比较后面字符；
• 若不等，从主串的下一字符起，重新与模式串的第一个字符比较
• 否则，匹配失败，返回值0

int Index_BF(SString S, SString T)
{
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length)
	{
		if (S.ch[i] == T.ch[j]) { ++i; ++j; }//主串和子串依次匹配下一个字符
		else { i = i - j + 2; j = 1; }//主串、子串指针回溯重新开始下一次匹配
	}
	if (j >= T.length)return i - T.length;//返回匹配的第一个字符的下标
	else return 0; //模式匹配不成功
}

BF算法时间复杂度：

若n为主串长度，m为子串长度，最坏的结果是

        主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位个比较了m次

总次数为：（n-m）*m+m = （n-m+1）*m

若m<<n，则算法时间复杂度为O(n*m)

KMP算法

        该算法较BF算法有较大改进，从而使算法效率有了某种程度的提高。

定义一个 next[j] 函数，，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

（1）

首先，主串"BBC ABCDAB ABCDABCDABDE"的第一个字符与模式串"ABCDABD"的第一个字符，进行比较。因为 B 与 A 不匹配，所以模式串后移一位。

（2）

因为 B 与 A 又不匹配，模式串再往后移。

（3）

就这样，直到主串有一个字符，与模式串的第一个字符相同为止。

（4）

接着比较主串和模式串的下一个字符，还是相同。

（5）

直到主串有一个字符，与模式串对应的字符不相同为止。

（6

这时，最自然的反应是，将模式串整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

（7）

一个基本事实是，当空格与 D 不匹配时，你其实是已经知道前面六个字符是"ABCDAB"。KMP 算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，而是继续把它向后移，这样就提高了效率。

（8）

怎么做到这一点呢？可以针对模式串，设置一个跳转数组int next[]，这个数组是怎么计算出来的，后面再介绍，这里只要会用就可以了。

（9）

已知空格与 D 不匹配时，前面六个字符"ABCDAB"是匹配的。根据跳转数组可知，不匹配处 D 的 next 值为 2，因此接下来从模式串下标为 2 的位置开始匹配。

（10）

因为空格与 Ｃ 不匹配，C 处的 next 值为 0，因此接下来模式串从下标为 0 处开始匹配。

（11）

因为空格与 A 不匹配，此处 next 值为 -1，表示模式串的第一个字符就不匹配，那么直接往后移一位。

（12）

逐位比较，直到发现 C 与 D 不匹配。于是，下一步从下标为 2 的地方开始匹配。

（13）

逐位比较，直到模式串的最后一位，发现完全匹配，于是搜索完成。

next 数组是如何求出的

next 数组的求解基于“真前缀”和“真后缀”，即next[i]等于P[0]...P[i - 1]最长的相同真前后缀的长度（请暂时忽视 i 等于 0 时的情况，下面会有解释）。我们依旧以上述的表格为例，为了方便阅读，我复制在下方了。

1. i = 0，对于模式串的首字符，我们统一为next[0] = -1；
2. i = 1，前面的字符串为A，其最长相同真前后缀长度为 0，即next[1] = 0；
3. i = 2，前面的字符串为AB，其最长相同真前后缀长度为 0，即next[2] = 0；
4. i = 3，前面的字符串为ABC，其最长相同真前后缀长度为 0，即next[3] = 0；
5. i = 4，前面的字符串为ABCD，其最长相同真前后缀长度为 0，即next[4] = 0；
6. i = 5，前面的字符串为ABCDA，其最长相同真前后缀为A，即next[5] = 1；
7. i = 6，前面的字符串为ABCDAB，其最长相同真前后缀为AB，即next[6] = 2；
8. i = 7，前面的字符串为ABCDABD，其最长相同真前后缀长度为 0，即next[7] = 0。

那么，为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢？举个代表性的例子：假如i = 6时不匹配，此时我们是知道其位置前的字符串为ABCDAB，仔细观察这个字符串，首尾都有一个AB，既然在i = 6处的 D 不匹配，我们为何不直接把i = 2处的 C 拿过来继续比较呢，因为都有一个AB啊，而这个AB就是ABCDAB的最长相同真前后缀，其长度 2 正好是跳转的下标位置。

有的读者可能存在疑问，若在i = 5时匹配失败，按照我讲解的思路，此时应该把i = 1处的字符拿过来继续比较，但是这两个位置的字符是一样的啊，都是B，既然一样，拿过来比较不就是无用功了么？其实不是我讲解的有问题，也不是这个算法有问题，而是这个算法还未优化，关于这个问题在下面会详细说明，不过建议读者不要在这里纠结，跳过这个，下面你自然会恍然大悟。

思路如此简单，接下来就是代码实现了，如下：

#include <stdio.h>
#include <string.h>
void get_next(char s[],int next[]);
int KMP(char s1[],char s2[],int next[]);
int main() {
	int i= 0;
	int next[1000];
	char s2[] = "ce";
	char s1[] = "ababce";
	get_next(s2,next);
    
	i=KMP(s1,s2,next);
    printf("%d\n",i);
    return 0;
}
void get_next(char s[],int next[])
{	
	int len=0;
    int i=0;//后缀 
    int j=-1;//前缀 
    next[0]=-1;//第一位符前面没有前缀，由公式知设为-1. 
    len=strlen(s);
    while(i<len)  
    {
        if(j==-1||s[i]==s[j])
        {
            i++;
            j++;
			next[i]=j;
        }
        else
        {
            j=next[j];
        }
    }
}
int KMP(char s1[],char s2[],int next[])
{
    int i=-1;
    int j=-1;
    int len1=strlen(s1);
    int len2=strlen(s2);
    while(i<len1&&j<len2)
    {
        if(j==-1||s1[i]==s2[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=len2)
        return i-len2+1;
    else
        return 0;
}

参考：

c++ - KMP 算法 - 经典算法与数据结构 - SegmentFault 思否