c语言中使用BF-KMP算法实例
2019/7/10 23:19:25
本文主要是介绍c语言中使用BF-KMP算法实例,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
直接上代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 255 //定义字符串的最大长度
typedef unsigned char SString[MAX_SIZE];//数组第一个保存长度
//BF
int BFMatch(char *s,char *p)
{
int i,j;
i=0;
while(i < strlen(s))
{
j=0;
while(s[i]==p[j]&&j < strlen(p))
{
i++;
j++;
}
if(j==strlen(p))
return i-strlen(p);
i=i-j+1; //指针i回溯
}
return -1;
}
//getNetx
void getNext(char *p,int *next)
{
int j,k;
next[0]=-1;
j=0;
k=-1;
while(j < strlen(p)-1)
{
if(k==-1||p[j]==p[k]) //匹配的情况下,p[j]==p[k]
{
j++;
k++;
next[j]=k;
}
else
{ //p[j]!=p[k]
k=next[k];
}
}
}
//KMP
int KMPMatch(char *s,char *p)
{
int next[100];
int i,j;
i=0;
j=0;
getNext(p,next);
while(i < strlen(s))
{
if(j==-1||s[i]==p[j])
{
i++;
j++;
}
else
{
j=next[j]; //消除了指针i的回溯
}
if(j==strlen(p))
{
return i-strlen(p);
}
}
return -1;
}
int main()
{
int a, b;
char s[MAX_SIZE], p[MAX_SIZE];
printf("请输入模式串:");
scanf("%s", &s);
printf("请输入子串:");
scanf("%s", &p);
a = BFMatch(s, p);
b = KMPMatch(s, p);
if(a != -1)
{
printf("使用BF算法:%d\n", a);
}
else
{
printf("未匹配\n");
}
if(b != -1)
{
printf("使用KMP算法:%d\n", a);
}
else
{
printf("未匹配\n");
}
system("pause");
}
结果
请输入模式串:lalalalalaaaa
请输入子串:lalaa
使用BF算法:6
使用KMP算法:6
请按任意键继续. . .
这篇关于c语言中使用BF-KMP算法实例的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享