串的模式匹配-KMP算法

阳光穿透心脏的1/2处 2022-05-08 12:16 181阅读 0赞

#include<stdio.h>
    #include<string.h>
    typedef struct String {
    	char base[5000];//字符数组
    	int nextval[5000];//nextval数组
    	int Length=0;
    	int HasGottenNext = 0;
    }cString;
    int KMPFind(cString parent, cString child)
    {
    	if (!child.HasGottenNext||parent.Length<child.Length)return 0;//在没有求得模式串的next数组的情况下就不能开始搜索匹配
    	int i,j;
    	for (i = 0, j = 0; i < parent.Length&&j < child.Length;)
    	{
    		if (parent.base[i] == child.base[j]) { j++; i++; }//相等则二者都移动到下一位
    		else {
    			if (j == 0) {i++; }//第一位就不相等，整个移动模式串开始比对
    			else if(child.nextval[j]!=0){ j = child.nextval[j] - 1; }//利用next数组移动模式串的下标
    			else { j = 0; i++; }//遇到不是第一位，但next数组对应值是0的，因为0-1=-1下标不能小于0，所以直接赋给j0，再将模式串整个移动
    		}
    	}
    
    	if(j>=child.Length)return 1;
    	return 0;
    }
    int BFFind(cString parent, cString child)//蛮力匹配
    {
    	int i, j;
    	for (i = 0; i <= parent.Length-child.Length; i++)
    	{
    		for (j = 0; j < child.Length; j++)
    		{
    			if (parent.base[i+j] != child.base[j]) { j = 0; break; }//遇到不相等的就将模式串对比位拨回第一位
    		}
    		if (j >= child.Length)break;
    	}
    	if (j >= child.Length)return 1;
    	return 0;
    }
    void SetNextvalArray(cString *Base)
    {
    	int i,j,n,maxEqual;
    	Base->nextval[0] = 0;
    	
    	**/*Base->nextval[1] = 1;弃
    	for (i = 2; i < Base->Length; i++)//依次求每位的next数组值，即求前i位长度子串的最长对称真子串值+1
    	{
    		n = 0;
    		maxEqual = 1;//对称真子串的最长度，初始为1
    		while (n<i-1)//不断变化的n长度真子串对比是否相等
    		{
    			for (j = 0; j <= n; j++)
    			{
    				if (Base->base[j] != Base->base[i - 1 - (n-j)]) {  break; }//i-1是当前正在求子串的主串的下标范围
    			}
    			if (j > n)maxEqual = n + 2;//当不跳出的经过for循环说明存在最大长度n+2的子串
    			n++;
    		}
    		Base->nextval[i] = maxEqual;
    	} */弃**
    
    
    	j = 0; i = 1;
    	while (i < Base->Length)//获取next数组的关键语句块
    	{
    		if (j == 0 || Base->base[i-1] == Base->base[j-1])
    		{
    			i++;
    			j++;
    			Base->nextval[i-1] = j;
    		}
    		else j = Base->nextval[j-1];
    	}
    
    	char ch;
    	for (i = 1; i < Base->Length; i++)//由next数组转为nextval数组
    	{
    		ch = Base->base[Base->nextval[i]-1];
    		if (ch == Base->base[i])Base->nextval[i] = Base->nextval[Base->nextval[i]-1];
    	}
    	Base->HasGottenNext = 1;//更新状态
    	return;
    }
    void PrintNextvalArray(cString *base)//显示nextval数组的内容
    {
    	int i;
    	if (!base->HasGottenNext)return;
    	for (i = 0; i < base->Length; i++)
    	{
    		printf("%2d",base->nextval[i]);
    	}
    	printf("\n");
    	return;
    }
    void PrintCharArray(cString *base)//显示串的内容
    {
    	printf("%s\n", base->base);
    	return;
    }
    void AssignCharArray(cString *Base)
    {
    	scanf("%s",&Base->base,5000);//获取输入的字符串
    	Base->Length = strlen(Base->base);//并赋值给cString的串长度成员变量
    	return;
    }
    int main()
    {
    	cString Parent, Child;
    	AssignCharArray(&Parent);
    	AssignCharArray(&Child);
    	SetNextvalArray(&Child);
    	//PrintNextvalArray(&Child);
    	printf("%d\n", KMPFind(Parent, Child));//用KMP算法匹配
    	printf("%d\n", BFFind(Parent, Child));//用BF算法匹配
    	return 0;
    }