【算法基础】BF算法与KMP算法

博主： Fivk
发布时间：2021 年 07 月 21 日
1108 次浏览
暂无评论
863字数
分类：算法基础

![](https://blog.fivk.cn/usr/uploads/2021/07/1138826613.png)

找了很多视频，在站找到了一个还不错的视频。

还有全套分类

[https://www.bilibili.com/read/cv8013121](https://www.bilibili.com/read/cv8013121)

就是代码少。不过自己写也差不多啦。

* 第一节KMP我写的课后作业

```cpp
#include<stdio.h>

int next[]={-1,0,0,0,0,1,2,3};

int KMP(char* s,char *t)
{
	int i=0,j=0;
	while(s[i]&&t[j])
	{
		if(s[i]==t[j])
		{
			i++;
			j++;
		}else{
			j=next[j];
			if(j==-1)
			{
				i++;
				j++;
			}
		}
	}
	if(!t[j])
	{
		return i-j;
	}else{
		return -1;
	}
}

int main()
{
	char *s="DABCDABD";
	char t[100];
	gets(t);
	int p=KMP(s,t);
	if(p!=-1)
	{
		printf("%d\n",p);
	}else{
		printf("查询不到字串\n");
	}
	return 0;
}
```

- 第二节课后写的作业

```cpp
#include<stdio.h>
#include<string.h>

int next[8]={-1,0};

void getNext(int next[],char s[])
{
	int i=0,j=-1;
	int len=strlen(s);
	while(i<len)
	{
		if(j==-1||s[i]==s[j])
		{
			i++;
			j++;
			next[i]=j;
		}else{
			j=next[j];
		}
	}
}

int KMP(char s[],char t[])
{
	int i=0,j=0;
	while(s[i]&&t[j])
	{
		if(s[i]==t[j])
		{
			i++;
			j++;
		}else{
			j=next[j];
			if(j==-1)
			{
				i++;
				j++;
			}
		}
	}
	if(!t[j])
	{
		return i-j;
	}else{
		return -1;
	}
}

int main()
{
	char s[]="DABCDABD";
	char t[100];
	gets(t);
	getNext(next,t);
	int p=KMP(s,t);

for(int i=0;i<strlen(t);i++) printf("%d ",next[i]);
	printf("\n");
	if(p!=-1)
	{
		printf("%d\n",p);
	}else{
		printf("查询不到字串\n");
	}
	return 0;
}
```

最后修改：2021 年 09 月 12 日