BF算法实现：复杂度O(m*n)
//在str的pos下标开始，判断是否包含sub字符串，包含则返回第一次匹配成功的开始下标 int BF(const char *str, const char *sub, int pos) { if (str == NULL || sub == NULL) return -1; int lenstr = strlen(str); if (pos < 0 || pos >= lenstr) return -1; int lensub = strlen(sub); int i = pos; //表示str的开始位置 int j = 0; //表示sub的开始位置 while (i < lenstr && j < lensub) { if (str[i] == sub[j]) //逐字符匹配上 { i++; j++; } else //此处没匹配上 { i = i - j + 1; //if中，i,j的增长量相同，则 i-j+1 表示原i的下一个坐标 j = 0; } } if (j == lensub) //上述if中，j++后，如果j==lensub则退出循环，且保证将子串全部匹配到 return i - j; //i减去增量j就是其开始位置 else return -1; }
KMP算法：复杂度O(m+n)
分析：
Kmp算法的特点： 主串位置 i不回退，但是子串 j 回退到该回退到的位置发生匹配失效后，在之前匹配成功的子串中找到两个最长的相等的真子串，两个真子串有如下两个特点: (1) 一个子串以0下标为开始; (2) 另一个下标以失配前的最后一个字符为结尾失配时如图：
4.用一次KMP算法后变化如图：
5. kmp算法的证明：
6. 手动求解子串对应的next数组
7. 程序中求解next数组的分析：
KMP代码实现：
static int *GetNext(const char *sub)//此方法不是最优的，其中包括一些无效的回退 { int len = strlen(sub); int *next = (int *)malloc(len*sizeof(int)); next[0] = -1; next[1] = 0; int j = 1; //表示失效时的下标 int k = 0; // k为失效 j回退的下标值，k永远小于 j while (j + 1 < len) //总共len个数据，2个已经确定，只需要再len-2次循环，从2~len-1就是len-2次 { if (k == 0 || sub[k] == sub[j])//k==0时,则表示回退到头开始 或 s[j+1]==p[k+1] --> next[j+1]=k+1 { next[++j] = ++k; //k==0时，j回退到 1 } else //s[j+1]!=p[k+1] --> k=next[k] { k = next[k]; //Pk!=Pj，且k一定小于j，而循环是为每个下标赋值，所以原k下标处的值之前已经有了 } } return next; } //KMP算法的特点：主串位置 i回退，但是子串 j回退到该回退到的位置 int KMP(const char *str, const char *sub, int pos) { if (str == NULL || sub == NULL) return -1; int lenstr = strlen(str); if (pos < 0 || pos >= lenstr) return -1; int lensub = strlen(sub); int i = pos; //表示str的开始位置 int j = 0; //表示sub的开始位置 int *next = GetNext(sub); while (i < lenstr && j < lensub) { if (j == -1 || str[i] == sub[j]) //逐字符匹配上， j==-1表示退无可退 { i++; j++; } else //此处没匹配上 { j = next[j]; } } delete[] next; if (j == lensub) //上述if中，j++后，如果j==lensub则退出循环，且保证将子串全部匹配到 return i - j; //i减去增量j就是其开始位置 else return -1; }
上述实现有一个问题：
假设模式串中q号位置失配了，那么我们下一次要跳转到next[q-1]号位置进行匹配，但是如果sub[q]==sub[next[q-1]]的话，那么我们这一次的匹配还是失败的，我们需要继续我们的next迭代过程，直到找到开始匹配的为止。
优化后代码如下：
static int *GetNextVal(const char *sub) { int len = strlen(sub); int *next = (int *)malloc(len*sizeof(int)); int *nextval = (int *)malloc(len*sizeof(int)); next[0] = -1; next[1] = 0; int j = 1; int k = 0; while (j + 1<len) { if (k == 0 || sub[k] == sub[j])//next[j+1] = k+1 { next[++j] = ++k; } else { k = next[k]; } } //获取修正的next值,去掉无效的回退 nextval[0] = -1; for (int i = 1; i<len; i++) { if (sub[i] == sub[next[i]]) { nextval[i] = nextval[next[i]]; } else { nextval[i] = next[i]; } } free(next); return nextval; } //KMP算法的特点：主串位置 i回退，但是子串 j回退到该回退到的位置 int KMP(const char *str, const char *sub, int pos) { if (str == NULL || sub == NULL) return -1; int lenstr = strlen(str); if (pos < 0 || pos >= lenstr) return -1; int lensub = strlen(sub); int i = pos; //表示str的开始位置 int j = 0; //表示sub的开始位置 //int *next = GetNext(sub); int *next = GetNextVal(sub); while (i < lenstr && j < lensub) { if (j == -1 || str[i] == sub[j]) //逐字符匹配上， j==-1表示退无可退 { i++; j++; } else //此处没匹配上 { j = next[j]; } } delete[] next; if (j == lensub) //上述if中，j++后，如果j==lensub则退出循环，且保证将子串全部匹配到 return i - j; //i减去增量j就是其开始位置 else return -1; }
