朴素字符串匹配算法
性能如下：
最优时间复杂度 | \(O(m)\) |
最坏时间复杂度 | \(O(m\times n)\) |
平均时间复杂度 | \(O(m\times n)\) |
字符串匹配最简单的算法就是朴素字符串匹配算法，其过程如下：
主串和子串匹配时， \(i,j\) 指针同时进一
主传和子串失配时， \(i=i-j+1, j=0\)
在字符串匹配过程中，由于子串的失配。主传指针 \(i\) 持续向前回溯，其简单实现如下：
int strMatch(const char *mainStr, const char *subStr) {
// 计算主串长度
int mainLen = strlen(mainStr);
// 计算子串长度
int subLen = strlen(subStr);
if (subLen > mainLen) return -1;
int i = 0, j = 0;
while (i < mainLen && (j < subLen)) {
if (mainStr[i] == subStr[j]) {
// 主串和子串匹配时指针同时向后移一位
++i; ++j;
} else {
// 主串和子串失配时指针向前回溯
i=i-j+1; j = 0;
}
}
if (j == subLen) return i-j;
return -1;
}根据算法导论，我们可以得到一个更加简要的写法：
bool strCmp(const char* a, size_t aBegin, const char* b, size_t bBegin, size_t len) {
for(size_t i = 0; i < len; ++i) {
if(a[aBegin + i] != b[bBegin + i]) return false;
}
return true;
}
int NATIVE_STRING_MATCHER(const char* T, const char* P) {
size_t n = strlen(T) - 1;
size_t m = strlen(P) - 1;
for(size_t s = 0; s <= (n - m); ++s) {
if(strCmp(P, 1, T, s + 1, m)) return (s + 1);
}
return -1;
}算法导论中数组的起始是零
KMP 匹配算法
KMP 算法的性能如下：
平均时间复杂度 | \(O(n+m)\) |
KMP 算法实现的核心是求解 next 数组，这部分内容相对而言比较简单：
int *CountNext(const char *P) {
int *next = (int*)malloc(strlen(P) * sizeof(int));
next[0] = 0;
int i = 1, j = 0;
for (int i = 1; i < strlen(P); ++i) {
if (P[i] == P[j]) {
// 如果匹配，next[i] = next[i-1]+1
// 这时候说明 P[0:j] == P [x:i]
// 这里 x 是将 i 向前推时 next 第一个不为零的位置
next[i] = next[i - 1] + 1;
++j;
} else {
// 如果发生失配，就将 j 指针移至开头
j = 0;
next[i] = 0;
}
}
return next;
}KMP 匹配和暴力匹配唯一的区别就是 i 指针不再回溯，只有 j 指针会回溯：
int KMP(const char *T, const char *P) {
int *next = CountNext(P);
const int n = strlen(T);
const int m = strlen(P);
int i = 0, j = 0;
for (; i < n && j < m; ++i) {
if (T[i] == P[j]) ++j;
else j = next[j];
}
if (j == m) return i - j;
return -1;
}附记
尽管这里只介绍了暴力匹配和 KMP 匹配算法，但是现实中还有其他比较好的算法，其性能有些甚至要优于 KMP 算法。参见 字符串匹配算法总结