串的模式匹配KMP算法C/C++代码实现_串的模式匹配代码

KMP算法思想：

KMP算法是对BF算法的改进，关键在不需回溯主串的i指针，且根据next数组的值移动子串的j指针。

匹配过程中匹配成功, 则i和j分别增1，否则，i不变， 而j退到next[j]的位置再比较，若相等， 则指针各自增1, 否则j再退到下一个next值的置，依次类推，直至下列两种可能：一种是j退到某个next值时字符比较相等，则指针各自增1, 继续进行匹配；另一种是j退到值为零（即模式的第一个字 符 ＂失配"),则此时需将模式继续向右滑动一个位置

next数组：

计算next值有两种方法：
第一种是根据前一位的next值，逐个比较是否相等（后面代码用此种方法）

第二种是求第n位时，比较前n-1位得出最长前后缀的匹配长度k，
则第n位的next值位k+1。(适用于手算做题)

nextval数组：

此数组是next的修正，弥补next数组有时的缺陷：例如模式"aaaab"在和主串"aaabaaaab"匹配时，当 i= 4、j= 4 时s.ch[ 4]不等于t.ch [ 4] , 由next(j)的指示还需进行 i= 4、j= 3, i= 4、j= 2, i= 4、j=1这3次比较。
计算nextval值有两种方法：
第一种是不依赖next数组值直接用观察法求得（见下面代码）
第二种是根据next数组值进行推理，比较。

代码如下：

#include<stdio.h>

#define MAXLEN 255

//串的顺序存储
typedef struct
{
   
	char ch[MAXLEN + 1];	//0号不用，从1开始
	int length;				//串的当前长度
}SString;
int next[MAXLEN];			//next数组
int nextval[MAXLEN];			//next修正数组

//KMP算法
//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在， 则返回值为0 
int Index_KMP(SString S, SString T, int pos)
{
   
	int i = pos;	//主串起始位置
	int j = 1;		//模式串起始位置

	while (i<=S.length && j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22