内容

        求一个字符串在另一个字符串中第一次出现的位置，要求：利用键盘输入两个字符串，一个设定为主串，另一个设定为子串，对这两个字符串应该用KMP算法，求出子串在主串中第一次出现的位置。

算法分析

        本题要完成KMP算法的实现，主要就是要使用串的存储结构来完成。首先要定义一个函数GetNext（）用来求next的值，然后求模式串t的next函数值并且存放到数组next当中，函数IndexKmp（）用来实现模式匹配算法。就是子串中的每一个字符依次和主串中的一个连续的字符序列相等，则成为匹配成功，反之则是匹配不成功，函数中Get Next（）是求出模板串t的next函数值并且存入到数组next中，函数IndexKmp（）为模式匹配函数，是用来模式串的next函数求t在主串s中第pos个字符之前的位置。当某个匹配位置不成功时，应该从字串的下一个位置开始新的比较。将这个位置的值存放到next数组当中，其中next数组的元素满足next[j]=k，表示当子串中的第j+1个字符发生匹配不成功的情况下，应该从子串的第k+1个字符开始新的匹配。

概要设计

KMP算法的实现

函数

void GetNext(DataType* t, int* next, int tlength) int IndexKmp(DataType* s, DataType* t, int pos, int tlength, int slength, int* next)

程序运行流程图如下：

 

 

#include <stdio.h>
#include<string.h>
#define MAXNUM 100
typedef char DataType;
typedef struct {
	DataType data[MAXNUM];
	int len;
}SString;
void GetNext(DataType* t, int* next, int tlength)//求模式串t的next函数值并存入数组next当中
{
	int i = 1, j = 0;
	next[1] = 0;
	while (i < tlength)
	{
		if (j == 0 || t[i] == t[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
	}
}
int IndexKmp(DataType* s, DataType* t, int pos, int tlength, int slength, int* next)//利用模式串的t的next函数求t在主串s中第pos个字符后面的位置
{
	int i = pos, j = 1;
	while (i <= slength && j <= tlength)
	{
		if (j == 0 || s[i] == t[j])//两个字符相同的情况，或者模式串j第一个字符进行比较时
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}
	if (j > tlength)
		return i - tlength;
	else
		return 0;
}
int main()
{
	int locate, tlength, slength, next[256];
	DataType s[256], t[256];
	printf("请输入第一个串（母串）：");
	scanf_s("%s",s,256);
	slength = strlen(s);
	printf("请输入第二个字符串（子串）：");
	scanf_s("%s", t, 256);
	tlength = strlen(t);
	GetNext(t, next, tlength);
	locate = IndexKmp(s, t, 0, tlength, slength, next);
	printf("位置匹配：%d\n",locate);
	return 0;
}