字符串--Kmp详解+代码

字符串查找问题:

        给定文本串text和模式串pattern,要求从文本串中找到模式串第一次出现的位置。

 解法:

         暴力解法(Brute Force):      时间复杂度O(M*N),空间复杂度O(1).

        kmp算法是对BF算法的改进,它是一种线性复杂度的算法,时间复杂度O(N),空间复杂度O(M)。  

    * 记文本串长度N,模式串M。   

暴力求解:

对每个文本字符(假设位置为i)匹配,从模式串第一个位置开始向后匹配,相同往后,不同则从i+1重新匹配。

kmp:

我们先假设有这样一种情况:要匹配的模式串没有一个相同,那你能想到一种线性复杂度的算法吗?

     假设目前A和B部分匹配上了,长度相同,i和j位置字符不同,按照暴力解法,我们要从k+1位置接着匹配。

   但是现在有前提条件:假设匹配串全都不同 那是不是只要从i位置重新匹配就行了。

 考虑这个很强的条件带给我们什么?   

       没错,就是匹配串的重复程度让我们知道从什么位置开始匹配更合理。

        搞定了匹配程度,kmp算法就很jian简单了。

step1:

         开一个数组next存储这种匹配程度,对于模式串的位置j,有next[j]=k,即

     p[0]~p[k-1]==p[j-k]~p[j-1].  则对位置j+1,考察p[j]

1.p[j]==p[k]

     next[j+1]=next[j]+1.

    2.p[j]!=p[k]

    记h=next[k];如果p[h]==p[j],则next[j+1]==h+1,

    重复此过程,若将h改为k,就是一个递归的过程。

最好自己画一下。

实现代码及其简单:

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000000;
char p[maxn],s[maxn];
int next[maxn];
int pattern_len;
void getnext()
{
	pattern_len=strlen(p);
	next[0]=-1;
	int k=-1,j=0;
	while(j<pattern_len-1)
	{
		if(k==-1||p[j]==p[k])
		{
			++j; ++k;
			next[j]=k;
		}else{
			   k=next[k];
		     }
	}
	
}
int kmp()
{
    int	ans=-1;
	int i=0,j=0;
	int n=strlen(s);
	while(i<n)
	{
		if(j==-1||p[j]==s[i])
		{
			i++; j++;
		}else  j=next[j];
		if(j==pattern_len)
		{
			ans=i-pattern_len+1;//字符以0开始,位置加一 
			break;
		}
	}
	return ans;
}
int main()
{
	while(1)
	{
		scanf("%s",s);//文本串 
		scanf("%s",p);//匹配串 
		getnext();
		
		printf("%d\n",kmp());
	}
	
  return 0;	
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Web项目聚集地

面试前你必须知道的三个排序算法

今天分享的是三种排序算法,在面试、实际编程中经常会碰到和使用到的,我会带领大家从分析排序算法技巧上以及代码实现上全面理解这一知识点的掌握。

15520
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

10240
来自专栏Java开发者杂谈

依赖数组特性的几种非比较排序算法

前言:   前面所讲的排序算法基本都是需要进行两个数依次比较,这种两个数依次比较的算法不依赖于数组重元素的特性并且有下界Ω(nlogn)。换句话说就是使用比较排...

49670
来自专栏Brian

数据分析利器-NumPy

---- 概述 NumPy类库是Python的一种开源的数值计算扩展。这种工具可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list s...

35380
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

399110
来自专栏目标检测和深度学习

常用排序算法总结(1)

14220
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

374100
来自专栏我是攻城师

理解桶排序算法原理

计数排序,基数排序,桶排序是所有排序算法里面时间复杂度能达到O(N)级别的算法,这主要原因是因为他们不采用基于比较的算法,前面的文章已经介绍了计数排序的原理,本...

72140
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

6410
来自专栏算法channel

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

442110

扫码关注云+社区

领取腾讯云代金券