【数据结构】KMP算法

/KMP算法/

sample in:
abckfbwejbwcv
ckf
sample out:3

对于代码的理解参考下面定义：
next数组的定义：
对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }。
匹配过程：
根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”

具体匹配过程可参考博客：
https://blog.csdn.net/dark_cy/article/details/88698736
https://www.cnblogs.com/dusf/p/kmp.html

#include
#include
#include
#define string_size 200//该程序定义的字符串最大长度 
#define error 1
#define ok 0
typedef char elem;
typedef int status;
typedef struct string
{
 	elem *ch;
 	int length;//字符串长度 
}string;//定义一个字符串结构体 
void get_next(elem t[],int *next)
{
 	int j=0,k=-1;//j作为遍历字符串的循环变量，k作为计数变量 
 	next[j]=k;//首先对next初始化为-1
 	while(t[j]!='')
 	{
	  	if(k==-1||t[j]==t[k])
	  	{
	   		j++;
	   		k++;
	   		next[j]=k;
	  	}//如果能匹配上则将k值赋给next[j]同时k值加一 ，此时k是相同子串的长度 
	  	else k=next[k];//如果不能匹配上，k回退。ps：但是j在继续向前走 
 	}
}//求模式串next值的函数 

status kmp(elem a[],elem b[]) 
{
	int next[string_size];
	get_next(b,next);
	int i=0,j=0;
	int lens=strlen(a),lensub=strlen(b);
	while(i=lensub)
	return i-j;//匹配成功则返回子串的位置 
	return -1;
}
int main()
{
 	elem a[string_size],b[string_size];
 	while(scanf("%s%s",a,b)!=EOF)
	{
 		printf("%dn",kmp(a,b)+1);
	}
}

/改进的kmp算法/

sample in:
abckfbwejbwcv
ckf
sample out:3

求nextval数组的方法与改进前的kmp有不同，但是匹配方式是相同的

j==-1表示i指向的字符串与j指向的字符串从第一个字符就不等i,j均后移，j==-1表示指向第一个字符之前

改进的KMP算法又添加了一个数组nextval, 它是在next基础之上计算出来的。
在求next数组的值的时候，判断一下，如果这个字符的next[j]=k，则next[j+1]不是直接等于k+1，而是判断一下，如果，j+1的字符等于k+1的字符，那么next[j+1]=next[k+1]。

#include
#include
#include
#define string_size 200
#define error 1
#define ok 0
typedef char elem;
typedef int status;
typedef struct string
{
	elem *ch;
	int length;
}string;
void get_nextval(char n[],int nextval[])
{
	int len=strlen(n);
	int i=0;
	int k=-1;
	nextval[i]=k;
	while(i=lensub)
	return i-j;//匹配成功则返回子串的位置 
	return -1;
}
int main()
{
 	elem a[string_size],b[string_size];
 	while(scanf("%s%s",a,b)!=EOF)
	{
 		printf("%dn",kmp(a,b)+1);
	}
	return 0;
}```