前言

字符串匹配算法又称模式匹配算法，该算法的目的是为了子串从主串中寻找是否有与其匹配的部分，

其可分为BF暴力检索、RK哈希检索、KMP、BM等等，本文仅介绍BF算法和KMP算法的实现，前者的时间复杂度是O(mn)，后者的时间复杂度是O(m+n)，本次文章就是对这两者的核心思路进行总结分析，以加强记忆。

一、BF算法

算法要求：假设有两个字符串，主串S和子串X，通过BF算法的逐步匹配，找到与子串匹配的主串部分，并返回第一次出现的下标。

算法思路如下：

代码实现如下（C语言）：

#include<stdio.h>
#include<assert.h>
#include<string.h>int BF(char* str, char* sub)//str代表主串，sub代表子串
{assert(str&&sub);//断言if (str == NULL || sub == NULL)//串为空值时直接返回-1{return -1;}int i = 0;//遍历主串int j = 0;//遍历子串int lenstr = strlen(str);//求出主串的长度int lensub = strlen(sub);//求出子串的长度while ((i < lenstr) && (j < lensub))//当子串遍历结束或主串遍历结束时，跳出循环{if (str[i] == sub[j])//匹配成功{i++;j++;}else//匹配失败{i = i - j + 1;j = 0;}}if (j >= lensub)//如果是因为子串遍历结束而跳出循环，说明匹配成功，返回下标{return i - j;}else//匹配失败，返回-1return -1;
}
int main()
{printf("%d\n", BF("ababcabcdabcde", "abcd"));//匹配成功，预期返回下标5printf("%d\n", BF("ababcabcdabcde", "abcds"));//匹配失败，返回-1printf("%d\n", BF("ababcabcdabcde", "ab"));//匹配成功，返回下标0return 0;
}

BF算法缺点：有大量匹配无效，效率低。

二、KMP算法

1.算法介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

2.算法思路

①next数组的求解：

例：有一个字符串ababcabc，求其对应的next数组。

解：第一个字符对应的next数组值为-1，第二个字符对应的next数组值为0，从第三个字符开始，判断第一个字符和第（n-1）个字符中是否有匹配的

数学分析：

假设next[i]=k，可推出p[0]...p[k-1]=p[x]...p[i-1]，既k-1-0=i-1-x，得x=i-k

即p[0]...p[k-1]=p[i-k]...p[i-1]

若能证得p[i]==p[k]，则可求得next[i+1]=k+1。

若p[i]!=p[k]，next[i+1]=??

举个例子：

代码分析：

void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{next[0] = -1;next[1] = 0;int i = 2;//当前i下标int k = 0;//前一项的kwhile(i < lensub){if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]{next[i] = k + 1;i++;k++;}else{k = next[k];//if条件不满足时则需将k回退到-1下标}}
}

附加知识： next数组的优化（nextval）

同样以例子来讲：

图中所示，当i=5时匹配失败，若按照next数组回退的话，到i=4时，依旧是a，匹配失败还得回退，每次回退都是相同的字符，这些回退无疑是无效的。而nextval数组就是对这一现象的优化。

3.整体代码实现

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{next[0] = -1;next[1] = 0;int i = 2;//当前i下标int k = 0;//前一项的kwhile(i < lensub){if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]{next[i] = k + 1;i++;k++;}else{k = next[k];//if条件不满足时则需将k回退到-1下标}}
}int KMP(char* str, char* sub, int pos)/*str:代表主串；sub:代表子串；pos:代表从主串的pos位置开始找*/
{assert(str&&sub);//断言if (str == NULL || sub == NULL)//字符串为空直接返回-1return -1;int lenstr = strlen(str);//求主串长度int lensub = strlen(sub);//求子串长度if (pos < 0 || pos >= lenstr)//pos位置不合法直接返回-1return -1;int *next = (int*)malloc(sizeof(int)*lensub);//开辟动态内存给next数组存放数据assert(next);GetNext(sub, next,lensub);//求出next数组int i = pos;//遍历主串int j = 0;//遍历子串while (i < lenstr&&j < lensub){if (j == -1 || str[i] == sub[j]){i++;j++;}else{j = next[j];}}free(next);next = NULL;if (j >= lensub){return i - j;}return -1;
}int main()
{printf("%d\n", KMP("ababcabcdabcde", "abcd", 0));//预期返回5printf("%d\n", KMP("ababcabcdabcde", "abcdf", 0));//预期返回-1printf("%d\n", KMP("ababcabcdabcde", "ab", 0));//预期返回0return 0;
}