共计 4167 个字符，预计需要花费 11 分钟才能阅读完成。
一. 朴素模式匹配算法
int strsub(const char* par, const char* sub, int pos)算法的基本思想：从主串 par 的第 pos 字符开始和子串 sub 的第一个字符比较，若相等，则继续捉个比较后续字符，否则则从主串的下一个字符起在重新和子串 sub 起始字符开始比较。以此类推，直至主串 par 中每个字符和子串 sub 的连续序列相等，则匹配相等，返回子串 sub 在主串 par 中的序号。否则匹配不成功，返回 -1. 下面是一个算法的实现
#include <stdio.h>
#include <string.h>
/* --------------------------------------------------------------------------*/
/**
* @brief 从主串中的指定位置查找指定的子串是否存在
*
* @param par 主串
* @param sub 子串
* @param pos 从主串中的指定位置
*
* @returns 如果存在返回在主串中的位置，不存在返回 -1
*/
/* ----------------------------------------------------------------------------*/int strsub(const char* par, const char* sub, int pos)
{
/* i 为主串当前位置的指针，j 为子串当前位置的指针 */
int i = pos, j = 0;
int par_len = strlen(par);
int sub_len = strlen(sub);
int ret = -1;
while (i < par_len && j < sub_len)
{if (par[i] == sub[j])
{
/* 当主串和子串当前字符相等时，指针前移 */
i++;
j++;
} else
{
/* 当有元素不相等时，则主串回退，子串从头开始 */
i = i - j + 1;
j = 0;
}
}
/* 如果所有的子串都能够匹配 */
if (j == sub_len)
{ret = i - j;}
return ret;
}
int main(int argc, char *argv[])
{int ret = strsub("abcdefg", "cde", 0);
printf("ret = %d\n", ret);
return 0;
}
朴素模式匹配算法简单，但是如果碰到碰到某些极端的情况时间负责度为 O(m*n), 假设主串长度为 m, 子串长度为 n, 下面是是一个极端的例子:
par: ababababc
sub: abcwhile 循环的次数为 7 * 3 ((m-n) * n)次，由此可以看出，当主串中存在多个部分匹配时，查找的效率是非常低的。
二。KMP 算法
我们来看上面的那张图，如果按照我们上面的朴素模式匹配算法的话，当 par[2] != sub[2]时，i 的值应该回溯，i 的值应该从 1 开始，但是你看我们图中，第二趟匹配的时候 i 没有从 1 开始，而是从 2 开始的。第三趟也是如此，保持上次匹配 i 的值不变。这就是我们下面介绍的 kmp 算法，每当一趟匹配过程中出现字符比较不相等是，不需回溯 i 指针，而是利用已经得到的 " 部分匹配 "，的结果将子串向右 ” 滑动 “ 尽可能远的一段距离，继续进行比较.
现在我们来讨论一般的情况，假设主串用 ‘p0p1....pm' 来表示，子串用 ’s0s1....sn' 来表示，从上例的分析可知，为了实现改进算法，需要解决如下问题：当匹配过程中产生 ” 失配 “（既 pi != sj)时，子串 ” 向右滑动 “ 可行的距离多远，换句话说，当主串中第 i 个字符与子串中第 j 个字符不相等时，主串中的第 i 个字符（i 指针不回溯）应与子串中的哪个字符在比较.
假设此时应与子串中的第 k 个字符继续比较，则子串中前 k - 1 个字符的必然要满足下列的关系式：
's0s1....s(k-1)' = 'p(i-k)p(i-k+1)....p(i-1)' 1 式
而已经得到的 ” 部分匹配 “ 的结果是
's(j-k)s(j-k+1)....s(j-1)' = 'p(i-k)p(i-k+1)....p(i-1)' 2 式
由 1 式和 2 式可得到下列等式
's0s1....s(k-1)' = 's(j-k)s(j-k+1)....s(j-1)' 3 式
若子串串中存在满足 3 式的两个子串，则当匹配过程中，主串（par)中的第 i 字符与子串 (sub) 中的第 j 个字符比较不相等时，仅需将子串（sub）向右滑动至子串中第 k +1(其标号为 k)个字符和主串（par）中的第 i 个字符对齐。此时，子串（sub）中头 k 个字符必定与主串（par）中第 i 个字符前的 k 个字符相等，由上面的推论得出。由此，匹配仅需从子串（sub）中第 k +1(其标号为 k)个字符与主串（par）第 i 个字符比较起继续执行.
若令 next[j] = k, 则 next[j]表明当子串（sub)中第 j 个字符与主串（par）中相应字符失配，在子串（sub）中重新和主串（par)中该字符进行比较的字符的位置。由此可引出子串的 next 函数的定义.
由此定义可推导出下列字符串的 next 函数值
kmp 算法是在已知字符串的 next 函数值的基础上执行的，那么，如何求得字符串的 next 函数值了。由上述讨论可见，此函数值仅取决于字符串本身而和相匹配的主串无关，我们可以定义出发用递推的方法求得 next 函数值
由定义可以 next[0] = -1;
设 next[j] = k, 这表明在子串中存在下列关系：
's0....s(k-1)' = 's(j-k)....s(j-1)'
其中 k 为满足 0 < k < j 的某个值，此时 next[j+1] = ? 可能有两种情况：
（1）若 s(k) = s(j), 则表明在子串中，存在
's0....s(k-1)s(k)' = 's(j-k)....s(j-1)s(j)'
这就是说 next[j+1] = k + 1, 既 next[j+1] = next[j] + 1;
(2)若 s(k) != s(j), 则表明
's0....s(k-1)s(k)' != 's(j-k)....s(j-1)s(j)'
此时可把求 next 函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是子串，而当前在匹配的过程中，已有 s0 = s(j-k), s1 = s(j-k+1), ...., s(k-1) = s(j-1), 则当 s(j) != s(k)时, 应将子串向右滑动至 next[k]个字符和主串中的第 j 个字符相比较. 若 next[k] = k', 且 p(j) = p(k'), 则说明有以下等式
‘s0....s(k'-1) = 's(j-k')....s(j-1)'
这就是说 next[j+1] = k' + 1 既 next[j+1] = next[k] + 1;
好了是时候给出 kmp 算法了：
#include <stdio.h>
#include <string.h>
#include <malloc.h>
void get_next(const char* sub, int* next)
{
int j = 0;
int k = -1;
int sub_len = strlen(sub);
next[0] = -1;
while (j < sub_len - 1)
{/* 这里的 sub[j]相当于主串，sub[k]相当于子串 */
if (k == -1 || sub[j] == sub[k])
{
j++;
k++;
next[j] = k;
} else
{k = next[k];
}
}
}
int strsub_kmp(const char* par, const char* sub, int pos)
{
/* i 为主串当前位置的指针，j 为子串当前位置的指针 */
int i = pos, j = 0;
int par_len = strlen(par);
int sub_len = strlen(sub);
int ret = -1;
/* 辅助空间 */
int* next = (int*)malloc(sizeof(int) * sub_len);
get_next(sub, next);
while (i < par_len && j < sub_len)
{/* j = - 1 的情况，就是由于 par[i] != sub[0]引起,j 的值已经回到 0, 不能再回，所以在下面执行 i ++, 将主串的索引加 1 */
if (j == -1 || par[i] == sub[j])
{
i++;
j++;
} else
{j = next[j];
}
}
/* 如果所有的子串都能够匹配 */
if (j == sub_len)
{ret = i - j;}
free(next);
return ret;
}
int main(int argc, char *argv[])
{int ret = strsub_kmp("abcdefg", "cde", 0);
printf("ret = %d\n", ret);
return 0;
}kmp 算法的时间负责度为 O(m+n), kmp 算法适用于当主串中有多个部分匹配时会非常高效。
前面定义的 next 函数在某些情况下尚有缺陷，列如子串 'aaaab' 在和主串 'aaabaaaab' 匹配时，当 i = 3, j = 3 时，出现不匹配的情况，有 next[j]的指示还需进行 i = 3, j = 2; i = 3, j = 1; i = 3, j = 0 这 3 次比较和第 4（标号为 3）个字符都相等，因此不需要再和主串的第 4 个字符相比较，而可以将子串一气向右滑动 4 个字符的位置直接进行 i = 4, j = 0 时的字符比较，这就是说，若按上述定义得到的 next[j] = k，而子串中 s(j) = s(k)，则当主串中字符 p(i)和 s(j)比较不相等时，不需要再和 s(k)进行比较，而直接和 p(next[k])进行比较，换句话说，此时的 next[j]应和 next[k]相同，下面是改进的 get_next 函数:
void get_next(const char* sub, int* next)
{
int j = 0;
int k = -1;
int sub_len = strlen(sub);
next[0] = -1;
while (j < sub_len - 1)
{if (k == -1 || sub[j] == sub[k])
{
j++;
k++;
if (sub[j] != sub[k])
{next[j] = k;
} else
{next[j] = next[k];
}
} else
{k = next[k];
}
}
}上面的算法描述参考严蔚敏的数据结构，详细的解析请看此书!
