KMP算法-C语言程序实现

灰太狼 2022-08-02 09:54 185阅读 0赞

原理参考ACM算法训练教程一书

//
    /*KMP算法*/ 
    #include<stdio.h>
    #include<string.h>
    #include<iostream>
    using namespace std;
    
    void getNext(char a[],int next[]){
    	int i,j;
    	next[1] = 0;
    	j = 0;
    	i = 2;
    	int m = strlen(a)-1; //从a[1]开始 
    	while(i<=m){
    		if(a[j+1] == a[i]){
    			j++; next[i++] = j;
    		}
    		else if(j==0){
    			next[i++] = 0;
    		}else if(j>0){
    			j = next[j];
    		} 
    	}
    }
    int match(char a[],char b[],int next[]){
    	int i=0,j=0;
    	int pos;
    	int n = strlen(a)-1;
    	int m = strlen(b)-1;
    	while(1){
    		if(i>n) {
    			pos = -1; break;
    		}
    		if(j==m){
    			//pos = i-j+1; break;
    			cout<<i-j+1<<"  "<<endl; j=next[j];
    		}
    		if(b[j+1] == a[i+1] ){
    			j++; i++;
    		}else{
    			if(j==0) i++;
    			else if (j>0){
    				j = next[j];
    			}
    		}
    	}	
    } 
    /* 
    int main()
    {	
    	//char b[] = "!ababbc"; 
    	char b[] = "!abab"; 
    	int l = strlen(b);
    	int *next = new int[l-1];
    	getNext(b,next);
    	int i;
    	for(i=1;i<=l-1;i++){
    		printf("%d ",next[i]);
    	}
    	cout<<endl;
    	char a[] = "!ababababbc";
    	int pos = match(a,b,next);
    	cout<<endl<<pos<<endl;
    }
    */
    //
    /*
    KMP应用： 求一个串中所有前缀等于后缀的子串长度 
    */
    void output(int i,int next[]){
    	while(next[i]>0){
    		cout<<next[i]<<" ";
    		i = next[i];
    	}
    }
    /*
    int main()
    {	
    	char b[] = "!ababa"; 
    	int l = strlen(b);
    	int *next = new int[l-1];
    	getNext(b,next);
    	int i;
    	for(i=1;i<=l-1;i++){
    		printf("%d ",next[i]);
    	}
    	cout<<endl;
    	output(l-1,next);
    	delete[] next;
    }
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】KMP算法（c语言）

include <stdio.h> include <string.h> include <stdlib.h> typedef...

男娘i/ 2024年04月17日 20:47/ 0 赞/ 101 阅读

相关 KMP 模式匹配算法（C语言版）

一、KMP算法的工作原理在我们进行字符串的模式匹配操作时，常用的算法有BF模式匹配算法和KMP模式匹配算法，其中BF模式匹配算法也就是常见的暴力解法，其时间复杂为O（m

逃离我推掉我的手/ 2024年02月23日 08:12/ 0 赞/ 85 阅读

相关 C语言strstr函数实现-KMP算法查找子串

KMP算法查找子串 -------------------- 代码实现： / 在字符串中查找一段子字符串 @param srcstr 原串 @param

短命女/ 2023年06月26日 08:20/ 0 赞/ 41 阅读

相关 C语言动态顺序串实现--KMP算法

数据结构C语言动态顺序串，相比于静态顺序串只是多了能增加最大容纳量函数的操作。 include <stdio.h> include <stdlib.h>

秒速五厘米/ 2022年12月16日 13:15/ 0 赞/ 204 阅读

相关 KMP算法（C语言）

本着对KMP算法的好奇，特地进行学习一下。文章目录一、简介二、构建next数组三、KMP算法的实现一、简介 > KMP算法是由

朱雀/ 2022年11月15日 11:46/ 0 赞/ 176 阅读

相关用C语言实现KMP算法,KMP算法纯C实现

该楼层疑似违规已被系统折叠隐藏此楼查看此楼我自己写的KMP算法： int nt\[256\]; void get\_next1(char\ T, int next\[

清疚/ 2022年10月15日 15:57/ 0 赞/ 187 阅读

相关 KMP算法-C语言程序实现

原理参考ACM算法训练教程一书 // /KMP算法/ include<stdio.h> include<string.h> incl

灰太狼/ 2022年08月02日 09:54/ 0 赞/ 186 阅读

相关 KMP算法C代码实现

一、初识KMP 理解KMP算法需要关注2个问题：（请注意：字符串下标从0开始。）当i指针与j指针失配时： 1、当母串和模式串不匹配时，i指针为什

Love The Way You Lie/ 2022年07月28日 09:49/ 0 赞/ 198 阅读

相关 KMP算法代码（C语言）

int next[1000000]; void get_next(char s[]) { int i=0; int j

野性酷女/ 2022年02月22日 18:08/ 0 赞/ 226 阅读

相关 KMP算法原理--C++//C实现

1 . 背景定义 KMP 用在在一个主文本字符串S内查找一个词W的出现位置设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b

爱被打了一巴掌/ 2021年11月23日 08:58/ 0 赞/ 316 阅读