kmp.cpp

C语言的课程设计。图书管理系统。有一些系统功能不怎么完善

#include"stdio.h"
#include"string.h"
#include"iostream.h"

int Index_KMP(char S[],char T[],int nextval[])//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
{
	int i;
	int j;
	i=0;j=1;
	while(i<=S[0]&&j<=T[0])
	{
		if(j==0||S[i]==T[j])
		{
			i++;j++;//继续比较后继字符
		}
		else j=nextval[j];//模式串向后移
	}
	if(j>T[0]) 
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void get_nextval(char T[],int nextval[])//求模式串T的next函数修正值并存入数组nextval
{
	int i=1,j=0;
	nextval[0]=T[0];
	nextval[1]=0;
	while(i<T[0])
	{
		if(j==0||T[i]==T[j])
		{
			++i;++j;
			if(T[i]!=T[j]) nextval[i]=j;
			else nextval[i]=nextval[j];
		}
		else j=nextval[j];
	}
}

int KMP(char main[],char child[])//模式匹配
{
	char cm[50];
	char cc[50];
	int nextval[50];
	int i=0,j=1;
	int flag;
	while(main[i]!='\0')
	{
		if(main[i]!=' ')
		{
			cm[j]=main[i];
			j++;
		}
		i++;
	}
	cm[j]='\0';
	cm[0]=j-1;
	i=0;j=1;
	while(child[i]!='\0')
	{
		if(child[i]!=' ')
		{
			cc[j]=child[i];
			j++;
		}
		i++;
		
	}
	cc[j]='\0';
	cc[0]=j-1;
	get_nextval(cc,nextval);
	flag=Index_KMP(cm,cc,nextval);
	return flag;
}