KMP字符串匹配

源代码:

#include<stdio.h>

typedef struct
{
	char ch;
	int len;
}string;

int next[100];
int local[100];
int address;

//构造字符串 
void CreateString(string s[])
{
	int i=0;
	char c;
	c=getchar();
	while(c!='\n')
		{
			s[++i].ch=c;
			c=getchar();
		}
	s[0].len=i;
}
//遍历串 
int getnext(string s[])
{
	next[1]=0;
	int i=1,j=0;
	while(i<s[0].len)
	{
		if(j==0||s[i].ch==s[j].ch)
		{
			i++;
			j++;
			next[i]=j;
		}
		else
		j=next[j];
	}
}

//KMP串匹配算法 
int kmp(string s[],string t[],int pos)
{
	int i=pos,j=1;
	while(i<=s[0].len&&j<=t[0].len)
	{
		if(j==0||s[i].ch==t[j].ch)
		{
			i++;
			j++;
		}
			else
     	j=next[j];
	}
	address=i-pos+1;
	if(j>t[0].len)
	{
		return i-t[0].len;
	}
	return 0;
}

//主函数 
int main(){
	string s[100];
    printf("请输入主串：\n") ;
	CreateString(s);
       
//字符匹配 
	char c;
	printf("请输入一个字符：\n");
	c=getchar();
	getchar();
	int count=0,local1,local2;
	for(int i=0;i<s[0].len;i++)
	{
		if(s[i].ch==c)
		{
			printf("at %d\n",i);
			count++;
		}
	}
	printf("appear %d\n",count);
	
	
	//子串匹配 
	string s1[100];
	printf("请输入一个子串：\n");
	CreateString(s1);
	getnext(s1);
	int pp=1;
	count=0;
	while(pp<s[0].len)
	{
		local1=kmp(s,s1,pp);
		if(local1)
		{
			
			count++;
			printf("at %d\n",local1);
		}
		pp+=address;
	}
	if(count)
	printf("appear %d\n",count);
	else
	printf("not find\n");
   
    //单词匹配 
	string s2[100];
    printf("请输入一个单词：\n");
    CreateString(s2);
	getnext(s2);
	pp=1;//串首 
	count=0;
	while(pp<s[0].len)
	{
		local2=kmp(s,s2,pp);
		if(local2)
		{
			//是否为单词的判定，首尾为空格 
			if((local2==1&&local2+s2[0].len==' ')||(local2+s2[0].len-1==s[0].len&&s[local2-1].ch==' ')||(s[local2-1].ch==' '&&s[local2+s2[0].len].ch==' '))
			{
			count++;
			printf("at %d\n",local2);
		}
		}
		pp+=address;
	}
	if(count)
	printf("appear %d\n",count);
	else
	printf("not find\n");
	 return 0; 
}
	

运行结果：

注意：主串可以任意，单词为首尾都是空格的字符串（当位于开头时，只需尾部为空格；当位于结尾时，只需开头为空格）