学步园

原理就不说了，学算法的都知道这基本上是查找一个字符串是否在另一个串中位置比较快的算法。代码如下：

#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
int next[MAXSIZE];
int S_lenth,D_lenth;
char source[MAXSIZE],detination[100];
void get_next()
{
	int i=1,j=0;
	next[1]=0;
	while(i<=D_lenth)
	{
		if(j==0||(detination[i-1]==detination[j-1]))
		{
			++i;
			++j;
			next[i]=j;
		}
		else
		{
			j=next[j];
		}
	}
}
int KMP()
{
	int i=0,j=1;
	while(i<=S_lenth&&j<=D_lenth)
	{
		if(j==0||(source[i]==detination[j-1]))
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	if(j>D_lenth)
	{
		return i-D_lenth;
	}
	else
		return 0;
}
int main()
{
	int i=0;
	printf("输入源串！！！\n");
	scanf("%s",&source);
	printf("输入模式串！！！\n");
	scanf("%s",&detination);
	S_lenth = strlen(source);
	D_lenth = strlen(detination);
	get_next();
	printf("next数组元素为：\n");
	for(i=1;i<=D_lenth;i++)
	{
		printf("%d ",next[i]);
	}
	printf("\n模式串开始于源串%d位置处",KMP());
	return 0;
}