C语言字符串模式匹配.doc

数据结构面试之十四——字符串的模式匹配

题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进

行了重写，供大家参考。

十四、字符串的模式匹配

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))

【核心思想】：是利用已经得到的部分匹配信息来进行后面的匹配过程。

正文 t t1 t2 t3 tm tn
模式 p p1 p2 p3 ¼. pm .

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

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

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

解读：

g 设定为-1
o 字符 o 之前没有匹配的字符。
o 字符 o（第 2 个）之前的字符（g，o）不同。
g 字符 g 之前的字符（g，o，o）前缀、后缀（如：g 与 o；go 与 oo）不匹配。
l 字符 l 之前的字符（g，o，o，g）前缀、后缀（如：g 与 g）相同，返回 1。
e 字符 e 之前的字符（g，o，o，g，l）前缀、后缀（如：goo 与 ogl）不同。

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

【KMP 算法实现】：

第一步：求解 next 数组。