【数据结构】— kmp算法和strstr函数

【数据结构】— kmp算法和strstr函数kmp算法和strstr函数注:现实生活中,字符串匹配在很多的应用场景里都有着极其重要的作用,包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等等,至此诞生了很多的算法,那么我们今天就来探索这两种经典的算法。一、概念分析首先我们需要了解到什么是kmp算法和strstr函数概念如下:KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R….

大家好,又见面了,我是你们的朋友全栈君。

引言

现实生活中,字符串匹配在很多的应用场景里都有着极其重要的作用,包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等等,至此诞生了很多的算法,那么我们今天就来探索这两种经典的算法。

一、概念分析

首先我们需要了解到什么是kmp算法和strstr函数
概念如下:KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。(来自百度百科)

strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是,则该函数返回 str1字符串从
str2第一次出现的位置开始到 str1结尾的字符串;否则,返回NULL。(来自百度百科)

分析

在这里我们很明显的看到,strstr作为最原始的算法,他的最差时间复杂度为O(len(s)*len(t)),效率是非常的低下的,而经过改良优化后的kmp算法则为O(m+n),两者进行一对比发现差距真的很大,而且kmp算法算然把字符串遍历了一遍,但如果不遍历一遍,怎么可能匹配的出来呢?

原理分析

对比发现,strstr函数对整个母串和字串都进行了多次的遍历,做了很多的重复工作,浪费了一些我们已经知道的信息,直接导致了时间的消耗,大大的降低了效率。例如,一个长度为9的t字符串abcdabcad,字串s为abca,当我们的指针走到t[4]的时候,发现匹配失败,此时s位置的指针已经走到了s[3]的位置,又得重新回到s[0],继续和t[4],进行匹配,重复此步骤,直到遍历完字符串t为止。这样子的话,重复匹配了s的字符n多次,所以效率极低。

strstr代码如下

	size_t Find(const char* str, size_t pos = 0) const 
	//(两个指针,字串和父串从第一个开始字符匹配,如果第一个字符匹配后,
	//开始逐个字符串匹配到最后一个,中途若有不同,字串退回开始,父串不变,继续重复操作,直至找到为止)
	{ 
   
		if (pos > _size)
		{ 
   
			cout << "pos位置有误报<<endl";
		}
		size_t index_str = 0;

		//若循环条件退出,要么找到了,要么找到结尾也没找到
		while (_str[index_str] != '\0')
		{ 
   
			if (_str[index_str] == *str)//从开头开始匹配字符
			{ 
   
				size_t  Find_index = index_str;
				size_t  str_index = 0;
				while (1)
				{ 
   
					//如果遍历完了str没有停下来,就表示找到了
					if (str[str_index] == '\0')
					{ 
   
						return index_str;
					}

					//如果不相等就结束循环
					if (_str[Find_index] != str[str_index])
					{ 
   
						break;
					}
					Find_index++;
					str_index++;
				}
				//跳出循环
			}
			//不匹配继续向前找
			index_str++;
		}

		return -1;
	}

KMP算法原理

基本操作

  • 我们要明白一个定义是next数组,这里就用到了一个相当重要的预处理思想,在我们不能直接求解问题的时候,我们可以先生成一个预处理数组用来记录我们一些信息。
    这个思想很关键,很重要。 就是一个字符串中最长的相同前后缀的长度加一, 例如字符串abcabcabc。
    那么它的next[1]一直到next[9],计算的是’a’, ‘ab’, ‘abca’, ‘abcab’,
    一直到’abcabcabc’相同的最长前缀和最长后缀,加一。前缀的意思是不能包含最后一个字符,后缀就是不能包含第一个字符。

    比如’a’,最长前后缀长度为0,原因上面刚说了,不包含。
    
    “abca”最长前后缀长度为1,即第一个和最后一个。
    
    “abcab”最长前后缀长度为2,即ab
    
    “abcabc”最长前后缀长度为3,即abc
    
    “abcabca”最长前后缀长度为4,即abca
    
    “abcabcabc”最长前后缀长度为6,即abcabc
    

图解

在这里插入图片描述

KMP原理

可能有人会想,为啥我们敢跳过那段长度为next的距离呢,再来一个图解。
在这里插入图片描述
竖线叫abc吧。

  • 主串叫t,子串交s 请看ab线中间包含的t中的子串,它在t中是一个以s[0]为开头,比黑块更长的前缀。
    请看ab线中间包含的t中的子串,它在t中是一个以b线前一个元素为结尾,比黑块更长的后缀。
    请回想黑块定义:这是目前位置之前的子串中,最长的相同前后缀。 请再想一想我们当初为什么能配到这里呢?

在这里插入图片描述

  • 这个位置之前,我们全都一样,所以多长的后缀都是相等的。其实就是,主数组后缀等于子数组后缀,而子数组前缀不等于子数组后缀,所以子数组前缀肯定不等与主数组后缀,也就是说,当前位置肯定配不出来这是比最长相同前后缀更长的前后缀啊兄弟。。。所以肯定不相等,如果相等,最长相同前后缀至少也是它了啊。有可能我的语言表达的不是很清晰,但是看着图解或许能更清楚一些。

三、复杂度分析

  • 时间复杂度是一个算法最为关键的性质,那么一起看一下这两者的时间复杂度对比,KMP在父串上的指针,两种情况,要么配了头一个就不对,就往后走了,这时用O(1)排除了一个位置。要么就是,配了n个位置以后配不对了,那不管next数组是多少,主串上的指针总会向后走n个位置的,所以每个位置还是O(1),这样看来,主串长度是len的话,时间复杂度就是O(len)啊。再看next数组求解的操作,一样的啊,最多就是子串的长度那么多。所以总体时间复杂度O(m+n),原来是O(m*n),这是一种非常聪明的方法,难怪可以称之为经典。

四、KMP算法代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
using namespace std;
typedef char* String;

//得到next数组
void Get_Next(String T, int *next)
{ 
   
	int j, k;
	j = 0;
	k = -1;
	next[0] = -1;
	while (j < strlen(T))
	{ 
   
		if (k == -1 || T[j] == T[k])
		{ 
   
			j++;
			k++;
			next[j] = k;
		}
		else
		{ 
   
			k = next[k];
		}
	}
}

//KMP算法
int KMP(String S, String T, int *next)
{ 
   
	int i = 0, j = 0;
	Get_Next(T, next);
	int slen = strlen(S);
	int tlen = strlen(T);

	while (i < slen && j < tlen)
	{ 
   
		if (j == -1 || S[i] == T[j])
		{ 
   
			i++;
			j++;
		}
		else
		{ 
   
			j = next[j];
		}
	}
	if (j == tlen)
	{ 
   
		return i - tlen;
	}
	else
	{ 
   
		return -1;
	}
}

void main()
{ 
   
	cout << "next就是输入的那一串字符每一个字符多对应的下标 " << endl;
	int N;
	cout << "请输入你想测试的次数:" << endl;
	cin >> N;
	while (N--)
	{ 
   
		cout << endl;
		cout << "请输入一串字符:" << endl;
		char S[255];
		char T[255];
		cin >> S >> T;
		int next[255];
		int i = 1;
		//cout << strlen(S) << endl;
		Get_Next(T, next);
		cout << "模式每一个字符对应的next的值为:" << endl;
		for (i = 0; i < strlen(T); i++)
		{ 
   
			printf("%d ", next[i]);
		}
		cout << endl;
		cout << "匹配出现的位置:" << KMP(S, T, next) << endl;

	}
	cout << endl;
	system("pause");
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/153013.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MySQL字符串分割_c语言中如何截取字符串

    MySQL字符串分割_c语言中如何截取字符串有分隔符的字符串拆分题目要求数据库中num字段值为:实现的效果:需要将一行数据变成多行实现的SQLSELECTSUBSTRING_INDEX(SUBSTRING_INDEX(‘7654,7698,7782,7788′,’,’,help_topic_id+1),’,’,-1)ASnumFROMmysql.help_topic…

  • JAVA生成uuid_oracle uuid生成

    JAVA生成uuid_oracle uuid生成packagetest.demo1;importjava.util.UUID;publicclassUUIDUtil{ publicstaticStringcreatUUID(){ returnUUID.randomUUID().toString().replace(“-“,””); } publicstaticvoidmain(String[]

  • 大数据平台解决方案

    大数据平台解决方案1、高负载和海量数据处理能力以云存储为基石,以云计算为处理核心,建立了海量的数据业务支撑的大数据平台。每天可以承受千万级PV的访问压力,支撑亿级用户及E8级各类数据存储如日志文件、图片、文档、影音等。基于此大数据支撑平台,不仅可以处理日以继夜增长的TB级数据增量,更能满足各类实时业务需求。2、业界领先的实时性在实时处理领域实现秒级突破,可以对各项业务数据惊醒实时查看与统计,方便客户快速

  • 计算距离矩阵的方法_矩阵的欧式距离

    计算距离矩阵的方法_矩阵的欧式距离给定一个 N 行 M 列的 01 矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:dist(A[i][j],A[k][l])=|i−k|+|j−l|输出一个 N 行 M 列的整数矩阵 B,其中:B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])输入格式第一行两个整数 N,M。接下来一个 N 行 M 列的 01 矩阵,数字之间没有空格。输出格式一个 N 行 M 列的矩阵 B,相邻两个整数之间用一个空格隔开。数据范围

  • vue axios跨域请求_vue跨域访问

    vue axios跨域请求_vue跨域访问vue中axios跨域请求1.axios是第三方库使用方法:使用npm:$npminstallaxios使用bower:$bowerinstallaxios使用cdn:<scriptsrc=”https://unpkg.com/axios/dist/axios.min.js”></script>axios…

  • listlength函数头文件_length函数

    listlength函数头文件_length函数length函数系统默认用户浏览8778请教MySQL高手:“length()”函数与“char_length()”函数的区别是什么?高手,您好:小弟的提问如题。希望高手能够为小弟举出一个能够展示length()函数与char_length()函数区别的例子。并且配合两个函数的作用机理,为小弟做一下这两个函数区别的讲解。谢谢…高手,您好:小弟的提问如题。希望高手能够为小弟举出一个能够展示le…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号