首页 > 编程语言 >kmp算法(c++)

kmp算法(c++)

时间:2024-08-07 17:23:17浏览次数:15  
标签:下标 int ne c++ next 算法 kmp 字符串

kmp算法的简单介绍

在这里插入图片描述

从主串中快速找到与要找的串的相同位置
如果使用暴力算法去求解这个问题,时间复杂度为O(i*j) => 很大
在这里插入图片描述
kmp算法则是对这类问题的优化
因整理过于麻烦,,详细的介绍可以参照这篇博客,,花时间看完就明白了,写的很棒!!!
kmp算法详细介绍
下面是自己学习的一些注意的地方

next[i]的介绍

以i为终点的后缀和从1开始的前缀相等,并且保证后缀的长度最长

ex: next[ i ] = j
在这里插入图片描述

p[ 1 , j] = p[ i - j + 1,i]
//p数组中从1到j这一段与 从i-j+1到i这一段相等 

在这里插入图片描述

当上面数组移动到S[i] 下面移动到p[j + 1]的时候,s[i] != p[j+1]

此时就要将 红颜色的线从前往后移动 要计算的是 从前往后最少需要移动多少 直接调用next[j]

移动完成之后 就变成第三段线段 从原本的j变成next[j]

然后就继续比较next[j]下面一位跟s[i]

在这里插入图片描述
最终就一直递归上面的操作 直到完全匹配为止

代码分析:

1、kmp匹配的过程
// j=1定义是因为  在比较的时候一直是p[j] 与 s[i+1]进行比较
//所以j要多加一个1去错位
	for (int i = 1, j = 0; i <= m; i++)
	{
    // while(j)的意思是j没有退回到起点 
    //j如果退回到起点(j == 0)含义就是需要重新开始匹配
    //s[i] != p[j+1] 出现不匹配的数字
    while(j && s[i] != p[j+1]) j = ne[j];
    //while循环结束有两种条件 
    //一个是j退回到了起点 
    //第二个是成功匹配了
    
    
    //如果他们两个已经匹配了,j就可以移动到下一个位置
    if(s[i] == p[j+1]) j++;
    if(j == n)
    {
        //3.匹配成功
    }
}
2、求next过程

在这里插入图片描述
跟第一个线段的绿色点位置进行比较

如果不同,则j = ne[j] 仍然不相同就 j = ne[ne[j]]

一直匹配到相等为止

//next[1]不需要去注意  因为j是从0开始的
//如果next[1] 中的q前面只有一个数  也就是说next[1]  == 》 p[0]  

	for (int i = 2, j = 0; i <= n; i++)
	{
		while (j && p[i] != p[j + 1]) j = ne[j];
		if (p[i] == p[j + 1]) j++;
		ne[i] = j;
	}
3、匹配成功的操作
			//输出起始位置
			printf("%d ",i - n);
			j = ne[j];

kmp字符串题目

给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N,表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M,表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。

数据范围

1≤N≤1e5
1≤M≤1e6

输入样例:

3
aba
5
ababa

输出样例:

0 2

#include <iostream>

using namespace std;
const int N = 10010, M = 100010;

int n, m;
//
char p[N], s[M];
int ne[N];

int main()
{
	// p + 1 跟 s + 1 表示下标从1开始
	cin >> n >> p + 1 >> m >> s + 1;

	//求next数组的过程
	for (int i = 2, j = 0; i <= n; i++)
	{
		while (j && p[i] != p[j + 1]) j = ne[j];
		if (p[i] == p[j + 1]) j++;
		ne[i] = j;
	}

	//kmp的匹配过程
	// i是为了遍历s数组
	// j是从0开始做,每一次试图往前走,看能否走通
	for (int i = 1, j = 0; i <= m; i++)
	{
		//j能否往后退 ,可以后退调用 j = ne[j]   
		while (j && s[i] != p[j + 1]) j = ne[j];
		//不能后退了之后还是不能走   条件都没有满足  i++ 看s串的下一个位置
		if (s[i] == p[j + 1]) j++;
		if (j == n)
		{
			//匹配完成
			//输出起始位置
			printf("%d ",i - j);
			j = ne[j];
		}
	}
	return 0;
}

标签:下标,int,ne,c++,next,算法,kmp,字符串
From: https://blog.csdn.net/weixin_73378557/article/details/140996872

相关文章

  • 【C++】string类
    ......
  • 【C++】一文带你学完 C++【完整版-附代码示例】
    本文篇幅较长,几乎涵盖了权威C语言教程【CppPrimerPlus】的所有可用知识点,建议点赞收藏关注方便后续阅读。附注:建议学完一个知识点后,同步进行编程练习以便于巩固掌握知识点;编程学习是重理论更重实践的一个过程,唯有多写多练才能快速掌握C++全教程正文开始......
  • C++进阶:1_C++中的继承
    C++中的继承一.继承的概念及定义1.继承的概念公共部分提取出来叫做:父类或者基类(正常类)继承父类的类叫做:子类或者派生类(派生类)继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段,它允许程序员在保持原有类特性的基础上进行扩展,增加功能,这样产......
  • C++:C++11介绍
    ✨✨✨学习的道路很枯燥,希望我们能并肩走下来!文章目录目录文章目录前言一、C++11简介二 统一的列表初始化2.1{}初始化2.2std::initializer_list三声明3.1auto 3.2decltype  3.3nullptr四范围for循环 五智能指针 六STL中一些变化 七右......
  • 四、神经网络(深度学习算法)
    4.1认识神经网络必要性当特征值只有两个时,我们仍可以用之前学过的算法去解决但当特征值很多,且含有很多个多次多项式时,用之前的算法就很难解决了例子:图像感知Recogonitionimage计算机识别汽车是靠像素点的亮度值  神经网络做法:4.2如何在神经网络上推理4.2.1......
  • C++ fmt
    Input/outputlibrarycppreferenceInput/outputlibrary有三种io库:OOP样式,基于流的io库基于print的系列函数C样式的IO函数基于流的'io'库基于流的'io'库是围绕抽象的io设备来进行组织的,这些抽象的设备允许使用相同的代码处理输入/输出文件,内存流,或定制......
  • 利用异或解决“只出现一次的数字“问题的C++解决方案
    该问题的输入是一个整数数组nums,其中除了一个数字之外,其余数字都出现了两次。任务是找到那个只出现一次的数字,并将其返回。 classSolution{public:  intsingleNumber(vector<int>&nums){    intval=0;    for(size_ti=0;i<nums.size();i++......
  • 【C/C++】 现有n个正整款,n<10000,要求出这n个正整数中的第k个最小整数(相同大小的整数
    现有n个正整款,n<10000,要求出这n个正整数中的第k个最小整数(相同大小的整数只计算一次)k≤1000,正整数均小于30000.第一行输入n和k,第二行输入有n个正整数的数组(有重复的数字)#include<iostream>#include<algorithm>usingnamespacestd;intmain(){intn=0,k=0;......
  • 代码随想录算法训练营day06|242.有效的字母异位词,349.两个数组的交集,202.快乐数,1.两数
    242.有效的字母异位词题目链接:https://leetcode.cn/problems/valid-anagram/description/我的代码:classSolution{public:boolisAnagram(strings,stringt){if(s.size()==t.size()){intrecord[26]={0};for(inti=0;i......
  • 路径规划算法之Dijistra算法、A*算法
    引言记录一下这段时间了解到的路径规划算法,并进行代码的实现目前主流的路径规划算法可以分为:基于采样,如RRT、RRT*、PRM基于节点,如Dijistra、A、D基于数学模型,如MILP、NLP基于生物启发式,如NN、GN多融合,如PRM-NodebasedDijistraalgorithm问题描述Dijistra算法主要......