首页 > 其他分享 >KMP

KMP

时间:2024-04-19 14:44:07浏览次数:16  
标签:匹配 int next 数组 KMP strlen

KMP算法
一个人能能走的多远不在于他在顺境时能走的多快,而在于他在逆境时多久能找到曾经的自己。
————KMP​

板子介绍
两个部分分别实现了next数组的构造
和匹配的过程。
本文均是从下标1开始的。(写题的时候就这么做即可,中间过程无虚任何改动)
最后打印的时候(看样例加和减即可)


#include <bits/stdc++.h>

using namespace std;

const int N = 100010000, M = 10010000; //N为模式串长度,M匹配串长度

char s[N], p[M];  //p是模式,s是被匹配 
int n, m;//n是p匹配串大小 
int ne[M]; //next[]数组,避免和头文件next冲突


int main()
{

    cin >> s+1 >> p+1;  //下标从1开始
	n=strlen(s+1);//计算大小 
	m=strlen(p+1);//计算大小 

    //求next[]数组
    for(int i = 2, j = 0; i <= m; i++)
    {
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    //匹配操作
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == m) //满足匹配条件,打印开头下标
        {
            //如:输出以0开始的匹配子串的首字母下标
            printf("%d\n", i - m+1); //(若从1开始,加1)
            j = ne[j];            //再次继续匹配
        }
    }
    
    //打印ne数组,也是从1开始 
    for(int i=1;i<=m;i++)
    {
    	cout<<ne[i]<<' ';
	}

    return 0;
}```

标签:匹配,int,next,数组,KMP,strlen
From: https://www.cnblogs.com/yzzyang/p/18145851

相关文章

  • KMP算法
    KMP算法KMP算法的核心思想是利用模式串自身的特性,在匹配过程中尽量避免回溯,以提高匹配的效率。它通过构建一个部分匹配表(也称为next数组),来指导匹配过程中模式串的移动位置,从而减少不必要的字符比较。KMP算法的基本步骤1.构建部分匹配表(next):遍历模式串,对于每个位置i,找出以......
  • KMP算法 Java实现
    Problem:28.找出字符串中第一个匹配项的下标目录解题方法思路构建next数组回溯查找复杂度Code解题方法构建next串回溯查找next串,最后下标思路通过最大前缀后缀能找到下一次未查找到后要回溯的位置构建next数组无论如何第一个数的下一次回溯位置肯定是0,因此next[......
  • KMP 相关
    KMPT1CensoringS给定一个文本串\(S\)和一个模式串\(T\),反复从\(S\)中删去最左边的完整出现的\(T\),然后把左右两部分接起来视作新的文本串\(S\),请问\(S\)的最终形式。\(1\leq|T|\leq|S|\leq10^6\)。T2OKR-PeriodsofWords我们认为\(Q\)是\(S\)的周期仅当......
  • 代码随想录算法训练营第9天 | 字符串(KMP算法) 28. 找出字符串中第一个匹配项的下标
    leetcode28.找出字符串中第一个匹配项的下标题目28.找出字符串中第一个匹配项的下标给你两个字符串haystack和needle,请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从0开始)。如果needle不是haystack的一部分,则返回-1。解题思路实现代......
  • 通俗易懂的KMP理论讲解(含手求Next数组)
    通俗易懂的KMP理论讲解(含手求Next数组)1.KMP算法介绍KMP算法的核心是利用匹配失败后的信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,尽量减少模式串与主串的匹配次数降低时间复杂度以达到快速匹配的目的。2.字符串的前后缀与公共前后缀2.1字符串的前缀字符串的......
  • KMP算法
    前言KMP算法:用于寻找s串中是否包含a串算法思路思路:暴力解法中使用(i,j)......
  • 探秘KMP算法:解密字符串匹配的黑科技
    KMP算法在正式进入KMP算法之前,不得不先引经据典一番,因为直接去理解KMP,你可能会很痛苦(别问,问就是我也痛苦过)。所以做好前面的预热工作非常非常重要,为了搞明白KMP,在没见到KMP算法的完整代码之前,请耐心的将前面的东西看完。一些相关的概念学习KMP算法,得明白它主要得作用......
  • ENSP通过 ISAKMP 方式建立 IPsec 隧道(采用证书认证)更新中
    第一步:证书准备cd/etc/pki/CAopensslreq-newkeyrsa:2048-x509-days365-out//CN-HN-SY-SYZY-XXJS-CA_ROOT(剩下的都按回车)cacert.pem-keyoutcakey.pemmvcakey.pemprivate/cd~/certsopensslreq-newkeyrsa:2048-new-outr1csr.csr-keyoutr1key.pem/......
  • KMP&&哈希算法
    KMP算法KMP算法是一种字符串匹配算法,用于匹配模式串P在文本串S中出现的所有位置。例如S=“ababac”,P="aba",那么出现的所有位置是13KMP算法将原本O(n^2)的字符串匹配算法优化到了O(n),其精髓在于next数组,next数组表示此时模式串下标失配时应该移动到的位置,(每次下标失配时,就是i!......
  • kmp板子
    书上讲的感觉不好理解,不如算法竞赛上分析的题目链接:https://www.luogu.com.cn/problem/P3375贴板子:#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<i......