找子串在主串中从第 i 个字符后首次出现的位置，称为串的模式匹配，最近学习了一点这一部分的内容，在此进行小结
一些定义
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
主函数
int main()
{
//主串
char S[MAX_SIZE];
//模式串
char T[MAX_SIZE];
printf("请输入主串:\n");
fgets(S,MAX_SIZE,stdin);
printf("请输入模式串:\n");
fgets(T,MAX_SIZE,stdin);
int len_s = strlen(S) - 1;
int len_t = strlen(T) - 1;
int id = -1;
//朴素配对法
//id = pusu_search(len_s,S,len_t,T);
//KMP
id = kmp_search(len_s,S,len_t,T);
printf("位置:%d\n",id);
return 0;
}
BF模式匹配算法
BF模式匹配算法，又叫朴素匹配算法。在遇到串的模式匹配这类问题时，相信很多人第一反应都是这样的最简单粗暴的算法。
大概过程：
先第一个进行匹配
1
acbbcabcacbca
|
bbcdabd
不能匹配，那就子串和主串进行匹配的第一个位置后移，直到可以进行匹配
2
acbbcabcacbca
|
bbcdabd
3
acbbcabcacbca
|||
bbcdabd
4
acbbcabcacbca
|
bbcdabd
依次类推，就这么暴力匹配，直到算出结果，比较简单，就直接贴代码了，注释已加：
//朴素匹配
int pusu_search(int len_s,const char *S,int len_t,const char *T){
int i = 0,j = 0;
while(i < len_s && j < len_t){ //相同
/* printf("i = %d\n",i); */
if(S[i] == T[j]){
i++;
j++;
}else{ //不相同
//与主串开始匹配的位置 + 1
i = i - j + 1;
//子串位置设置为 0 重新开始匹配
j = 0;
}
}
//匹配成功
if(j == len_t){
//返回位置
return i - j;
}
//不能匹配
return -1;
}
若 n 是S的长度，m是P的长度，时间复杂度在O(m*n)，非常费时间，而KMP算法的时间复杂度可以简化为O(m+n)
KMP模式匹配算法
我们先来用朴素匹配来匹配一下这两个串
abcabcababccacb
||
ababcc
此时下一位不匹配，用朴素法的话，又要一步步尝试,直到这里
abcabcababccacb
|
ababcc
有没有一种好的方法，可以让省略中间的步骤，直接到这一步呢？
为解决这个问题 KMP 算法诞生了
提前根据子串处理出一个相对应的 next 数组，
让控制主串匹配位置的 i 不回溯，留在原地，
用在 next 数组中记录的 与子串相对应位置 的值来控制子串匹配位置的 s，
更清晰的KMP流程请点击阮一峰的字符串匹配的KMP算法流程
计算每一组的最长相同的前缀和后缀
这里给出 next 数组的求法，如本例
个数 串 最长相同前后缀
0 a 无
0 a b 无
1 a b a a
2 a b a b ab
0 a b a b c 无
然后我们规定其第一个为 -1 ，然后将上面计算出的个数直接填上去
i 0 1 2 3 4 5
S a b a b c c
next -1 0 0 1 2 0
这样，当我们进行子串与主串匹配时，当单个字符相等时，继续匹配下一个，当单个字符不同时，我们不用回溯 i ，只需要对子串要与主串进行匹配的字符的位置下标（len）进行操作，
代码实现如下，具体注释已加：
//打印数组函数
void print_num(const int a[],int n){
for(int i = 0;i < n;i++){
printf("%d =%d\n",i,a[i]);
}
return;
}
//计算next数组
void get_next(int *next,const char *T,int len_t){
//先初始化为-1
next[0] = -1;
//后缀单个字符数组下标
int i = 0;
//前缀单个字符数组下标
int j = -1;
while(i < len_t){
if(j == -1 || T[i] == T[j]){ //相同，继续匹配
//同时后移
i++;
j++;
//赋值
next[i] = j;
}else{ //不同，j回溯
/**代码下面解释中的第二个原因语句位置**/
j = next[j];
/********************************/
}
}
//打印查看next
/* print_num(next,len_t); */
return;
}
可能有些朋友会问，len == -1 的意义是什么呢？其实有两点：
(1)在第一次进入 while 循环时，len 初始值为 -1，直接进行S[i] == S[len]的话，会边界溢出;
(2)代码中 len = next[len] 语句中 len 不断后退回溯变成 -1 ，在进行S[i] == S[len]时，会边界溢出;
本题中的情况：
abcabcababccacb
||
ababcc
此时只需要将控制子串的下标 s 赋值为next[s]，即 0 ，然后就可以直接移动子串，直接重新开始匹配
相当于直接到达这一步:
abcabcababccacb
|
ababcc
KMP算法实现，其中注释已加：
//KMP算法
int kmp_search(int len_s,const char *S,int len_t,const char *T){
int next[MAX_SIZE];
//计算对应的数组
//未优化
get_next(next,T,len_t);
//优化后
/* get_nextval(next,T,len_t); */
int i = 0,j = 0;
while(i < len_s && j < len_t){
/* printf("i = %d,j = %d\n",i,j); */
if(j == -1 || S[i] == T[j]){ //匹配成功
i++;
j++;
}else{ //匹配失败，进行跳转
j = next[j];
}
}
//匹配成功
if(j == len_t){
return i - j;
}
//不能匹配
return -1;
}
KMP算法优化
KMP算法的优化主要在于对优化 next ，形成新的nextval
i 0 1 2 3 4 5
S a b a b c c
next -1 0 0 1 2 0
我们还是先来看这个例子，
当我们再用 next 进行匹配时，当匹配到 i = 3 时，如果匹配不成功，就会跳转到 i = 1 的位置，但是两个位置上的字符其实是一样的，这样就又要进行匹配，继而增加了时间，多做了无用功
所以，我们在生成 nextval 时就要避免这个问题，让当 i = 3,和i = 1处的字符相同时，让其继续向前寻找真前缀
i 0 1 2 3 4 5
S a b a b c c
nextval -1 0 -1 0 2 0
这样，我们就得到的 nextval 就表示的是真前后缀长度，但不一定是最长的，使用优化版可以让我们相比较与以前的版本，更加快速地找到答案
代码实现，注释已加：
//计算nextval数组
void get_nextval(int *nextval,const char *T,int len_t){
nextval[0] = -1;
int i = 0;
int j = -1;
while(i < len_t){
if(j == -1 || T[i] == T[j]){
i++;
j++;
/* ***********************这里不同************************** */
if(T[i] != T[j]){
nextval[i] = j;
}else{
nextval[i] = nextval[j];
}
/* ******************************************************* */
}else{
j = nextval[j];
}
}
//打印查看nextval数组
print_num(nextval,len_t);
/* getchar(); */
return;
}
一点关于 next 和 nextval 的补充：
next 数组表示最长的相同前后缀长度，用它还可以解决类似字符串重复的问题，而 nextval 则不行。
至于具体实现与实际情况，暂时还没有了解过，以后有机会的话再研究研究