数据结构面试之十四——字符串的模式匹配
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

十四、字符串的模式匹配
1. 模式匹配定义——子串的定位操作称为串的模式匹配。

2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法）
【算法思想】：
第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。

第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。

比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。

对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。

【算法实现】：
//普通字符串匹配算法的实现
int Index(char* strS, char* strT, int pos)
{
//返回strT在strS中第pos个字符后出现的位置。

int i = pos;
int j = 0;
int k = 0;
int lens = strlen(strS);
int lent = strlen(strT);
while(i < lens && j < lent)
{
if(strS[i+k] == strT[j])
{
++j; //模式串跳步
++k; //主串(内)跳步
}
else
{
i = i+1;
j=0; //指针回溯，下一个首位字符
k=0;
}
}//end i
if(j >= lent)
{
return i;
}
else
{
return 0;
}
}//end
[算法时间复杂度]：设主串长度为m,模式串的长度为n。

一般情况下n<m。

最好时间复杂度：举例，主串S=”ababaababc”; 模式串T=”abab”; 比较次数为n次。

时间复杂度为O（n）。

最坏时间复杂度：举例，主串S=”000000000000000000001”（20个0，1个1）; 模式串T=”00001”（4个0，1个1）;比较次数为17*5次。

时间复杂度接近O（m*n）。

整个匹配过程需要多次回溯（有16次回溯）。

平均时间复杂度：O(m*n)。

[空间复杂度]：O（1），不需要额外开辟空间存储。

3. KMP算法——是一种线性时间复杂的字符串匹配算法，它是对BF算法改进。

[时间复杂度]：O(m+n)，即：O(strlen(S) + strlen(T))
[空间复杂度]：O(n)，即：O(strlen(T))
【核心思想】：是利用已经得到的部分匹配信息来进行后面的匹配过程。

【next（j）定义】:表示当p i不等于t r时，下一次将p next[i]与t r开始继续后继对应字符的比较。

其中next[0]=-1,表明当p0不等于t r时，将从p-1与t r开始继续后继对应字符的比较；显然p-1是不存在的，我们可以将这种情况理解成下一步将从p0与t r+1开始继续后继对应字符的比较。

举例说明1：模式串p=“google”,对应的next[j]={-1,0,0,0,1,0}。

解读：
举例说明2：模式串p=“abaabcaba”，对应的next[j]={-1,0,0,1,1,2,0,1,2}。

【KMP算法实现】：
第一步：求解next数组。