首页 > 其他分享 >c语言实现的KMP(包含各种版本)

c语言实现的KMP(包含各种版本)

时间:2024-11-02 11:15:48浏览次数:6  
标签:包含 len2 int s2 s1 next ++ 版本 KMP

学KMP的时候(很多算法都是这样)感觉真的就是To talk is easy,show your code。索性把两种KMP以及连续的KMP都写好一遍传上来,已经经过数据集验证正确性,可以放心使用。代码也是尽量比较简洁明了的风格,也方便我和大家复习自用。原理解析的话因为画图解释需要一点时间,有需要的话可以评论区@我,后面可以再找时间写一个详细的解析,不过KMP网上解析的视频也很多了,我看的是左程云左神学的,他讲的是真的很不错。不过代码没有用他的代码,用了这种更为简练的版本(速度肯定是一样快的,而且他那个版本思路要更清晰)。闲话休提,上代码。

'''cpp
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//警告 下面的一些++j,i++等的混合写法,有时候编译器会出错!!
//写开来不会耗费多少时间!!!
//保证安全性!!!!

//求nextVal数组


int *getNextVal(char *s, int length) {
	int *next = (int *)malloc (sizeof(int) * (length + 1));
	next[0] = -1;
	int i = 0, j = -1;
	while (i < length) {
		if (j == -1 || s[i] == s[j])
			next[++i] = ++j;
		else
			j = next[j];
	}
	return next;
}


//用nextVal数组实现的KMP,就是next[0]=-1那个


void KMPVal(char s1[], char s2[]) {
	int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
	int *next = getNextVal(s2, len2);
	int i = 0, j = 0;
	while (i < len1 && j < len2) {
		if (j == -1 || s1[i] == s2[j]) {
			j++;
			i++;
		} else
			j = next[j];

	}
	if (j == len2)
		printf("%d", i - j + 1);
	else
		printf("no finding");

}


//nextVal数组实现的连续KMP

void continueKMPVal(char s1[], char s2[]) {
	int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
	int *next = getNextVal(s2, len2);
	int i = 0, j = 0;
	while (i < len1) {
		if (j == -1 || s1[i] == s2[j]) {
			i++;
			j++;
		} else
			j = next[j];
		if (j == len2) {
			printf("%d ", i - j + 1);
			j = next[j];
		}


	}

}

//求next数组,next【0】=0那个

int *getNext(char *s, int length) {
	int i = 1, j = 0;
	int *next = (int *)malloc(sizeof(int) * length);
	next[0] = 0;
	while (i < length) {
		if (s[i] == s[j])
			next[i++] = ++j;


		else if (j > 0)
			j = next[j - 1];
		else
			next[i++] = 0;
	}
	return next;

}

//next数组实现的KMP

void KMP(char s1[], char s2[]) {
	int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
	int *next = getNext(s2, len2);
	int i = 0, j = 0;
	while (i < len1 && j < len2) {
		if (s1[i] == s2[j]) {
			i++;
			j++;
		} else if (j > 0)
			j = next[j - 1];
		else
			i++;
	}
	if (j == len2)
		printf("%d", i - j + 1);
	else
		printf("no finding");

}

//next数组实现的KMP


void continueKMP(char s1[], char s2[]) {
	int len1 = (int)strlen(s1), len2 = (int)strlen(s2);
	int *next = getNext(s2, len2);
	int i = 0, j = 0;
	while (i < len1) {
		if (j == -1 || s1[i] == s2[j]) {
			i++;
			j++;
		} else
			j = next[j - 1];
		if (j == len2) {
			printf("%d ", i - j + 1);
			j = next[j - 1];
		}


	}



}

int main() {
	char s1[100], s2[100];
	gets(s1);
	gets(s2);
	




}

标签:包含,len2,int,s2,s1,next,++,版本,KMP
From: https://blog.csdn.net/clannad551/article/details/143448037

相关文章

  • 解决 System.Runtime.CompilerServices.Unsafe 程序集版本不匹配问题
    你是否在.NET文件上传中遇到过令人头疼的引用错误?今天我们就来深入探讨如何解决System.Runtime.CompilerServices.Unsafe引用错误1.错误现象在文件上传操作中,当处理特定文件格式(如.xlsx)时,代码workbook=newXSSFWorkbook(myfile.InputStream);出现异常。异常信息为......
  • Vllm进行Qwen2-vl部署(包含单卡多卡部署及爬虫请求)
    1.简介阿里云于今年9月宣布开源第二代视觉语言模型Qwen2-VL,包括2B、7B、72B三个尺寸及其量化版本模型。Qwen2-VL具备完整图像、多语言的理解能力,性能强劲。相比上代模型,Qwen2-VL的基础性能全面提升,可以读懂不同分辨率和不同长宽比的图片,在DocVQA、RealWorldQA、MTVQA等基......
  • LLaVA-1.5:强大的多模态大模型(包含论文代码详解)
    1.概述LLaVA是一个由威斯康星大学麦迪逊分校、微软研究院和哥伦比亚大学的研究人员开发的大型语言和视觉助手。它是一个端到端训练的大型多模态模型,结合了视觉编码器和语言模型,用于通用的视觉和语言理解。 微软研究院、威斯康星大学的研究人员在LLaVA基础之上,继续开源了LLa......
  • [编程笔记] 搞人心态的代码含毒事件 “svn无法成功完成操作因为文件包含病毒或潜在的
    今天突然冒出来的问题,烦死了! svn拉取代码报毒了,不用想,基本就是下面几个可能性:1、某人提交的代码有毒2、电脑上的第三方杀毒软件引发3、WindowsDefender误判报毒的代码是一个dll文件,鬼知道写的什么,没有去深究,杀毒软件最近......
  • Adobe After Effects各版本安装包下载与安装
    1、安装包  我用夸克网盘分享了AfterEffects2024:链接:https://pan.quark.cn/s/fac88adbac44提取码:9ZMWAfterEffects2023:链接:https://pan.quark.cn/s/d41a0a447b93提取码:4pwMAfterEffects2022:链接:https://pan.quark.cn/s/0070a59da58d提取码:Eij1AfterEffect......
  • Adobe InDesign 各版本下载与安装
    1、安装包  我用夸克网盘分享了「AdobeInDesign2023.rar」,点击链接即可保存。打开「夸克APP」,无需下载在线播放视频,畅享原画5倍速,支持电视投屏。链接:https://pan.quark.cn/s/526c259dad6f提取码:MfMX AdobeInDesign2022:链接:https://pan.quark.cn/s/c7ee80a21975提......
  • Delphi7 对比两个文件版本
     functionCompareFileVersion(strVerNew:String;strVerOld:String):boolean;vari:integer;newCount:Integer;oldCount:Integer;slVerNew:TStringList;slVerOld:TStringList;beginResult:=True;slVerNew:=TStringList.Create;slVe......
  • Office、Visio、project 各版本资源下载
    1、Office安装包资源下载(部分需要联网以及安装包内包含激活工具)   Office365:链接:https://pan.quark.cn/s/e680210d9869提取码:e8vjOffice2003:链接:https://pan.quark.cn/s/e2fb7135c8fc提取码:FgueOffice2010:链接:https://pan.quark.cn/s/4de780bbf20c提取码:Kb8gOf......
  • .NET Framework 3.5/4.0/4.5/4.6版本离线版安装包下载
    1、安装包资源下载.NETFramework各版本:链接:https://pan.quark.cn/s/c68076e7865a提取码:tiN7  2、安装教程(.NETFramework4.7为例)1)       安装包双击打开 2)       勾选我同意,点击安装 3)       安装成功,点击关闭,查看系统设置,应用......
  • AP3464 包含多重保护功能:过温保护,输出短路保护和输入欠压/过压保护等。
    产品描述AP5103是一款效率高,稳定可靠的LED灯恒流驱动控制芯片,内置高精度比较器,固定关断时间控制电路,恒流驱动电路等,特别适合大功率LED恒流驱动。AP5103采用ESOP8封装,散热片内置接SW脚,通过调节外置电流检测的电阻值来设置流过LED灯的电流,支持外加电压线性调光,最大电......