首页 > 其他分享 >洛谷题单指南-字符串-P3375 【模板】KMP

洛谷题单指南-字符串-P3375 【模板】KMP

时间:2024-10-09 17:14:13浏览次数:7  
标签:子串 后缀 洛谷题 ++ Next int KMP P3375 size

原题链接:https://www.luogu.com.cn/problem/P3375

题意解读:给定两个字符串:原串s,模式串p,求p在s中出现的所有位置,并输出p的长度为1~p.size()的子串的最长相同真前、后缀的长度。

解题思路:

KMP模版题,分两问,第一问通过KMP核心算法实现,第二问输出模式串的Next数组内容,接下来一一解读。

1、字符串相关概念

子串:字符串中挑选一段连续的字符形成的字符串,挑选的字符连续。

子序列:字符串中从前到后挑选若干字符形成的字符串,挑选的字符不一定连续。

前缀/真前缀:字符串中从开头挑选一段子串,称为前缀,如果前缀不等同于原来的字符串,称为真前缀。

后缀/真后缀:字符串中选一段包括结尾的子串,称为后缀,如果后缀不等同于原来的字符串,称为真后缀。

2、暴力法字符串匹配

要查找字符串p在s中出现的位置,直观做法可以通过暴力枚举,采用双指针i遍历s,j遍历p,进行一一比对即可,代码如下:

for(int i = 0; i < s.size(); i++)
{
    int j = 0;
    while(s[i + j] == p[j]) j++;
    if(j == p.size())
    {
        cout << i + 1 << endl; //出现的位置是字符串的下标再加1
    }
}

其核心思想是,从s的每一个位置开始,判断是否有子串和p的每一个字符都相等,如果中间有一个字符不相等,i往后移一位,j回到开头,重新比较。

整个过程算法时间复杂度为s.size() * p.size()。

3、KMP算法思路

KMP算法主要是针对暴力算法的问题进行优化,当发现不匹配时,通过减少不必要的指针回退,从来提升双指针算法的效率。

整个过程的核心就是当发现不匹配时,i不动,j移动到合适的位置继续匹配,由于此时p中j前面的内容都已经和s中i前面的内容匹配,

因此针对这一段已经匹配的内容s[0]~s[7]或者p[0] ~ p[7],如果能计算出其最长相同的真前、后缀长度,那么就可以将j移动到合适的位置。

如图中所示,此时最长相同真前后缀长度为5,因此可以将j移动到下标5的位置,继续和i=8进行匹配。

这样一来,整个过程时间复杂度可以认为是s.size() + p.size()。

4、Next数组

上面已经介绍,当发现不匹配的位置s[i] != p[j]时,j应该回退到p[0]~p[j-1]子串的最长相同真前后缀长度的位置,

那么,可以定义Next[j]表示从p[0]~p[j]子串的最长相同真前后缀长度

KMP的核心代码过程为:

int slen = s.size();
int plen = p.size();
for(int i = 0, j = 0; i < slen; i++)
{
    while(j && s[i] != p[j]) j = Next[j - 1]; //如果不匹配,j跳转到Next[j-1]
    if(s[i] == p[j]) j++; //如果匹配,j++,继续比较
    if(j == plen) 
        找到一个完整的匹配;
}

Next数组初始化

由于Next数组的计算只与p相关,因此可以提前对其进行初始化,我们仍然从暴力思路开始

P:A A C A A C A A A A

Next数组 子串 最长相同真前后缀长度
Next[0]  P[0] ~ P[0]:A 0
Next[1]  P[0] ~ P[1]:A A  1
Next[2]  P[0] ~ P[2]:A A C  0
Next[3]  P[0] ~ P[3]:A A C A  1
Next[4]  P[0] ~ P[4]:A A C A A  2
Next[5]  P[0] ~ P[5]:A A C A A C  3
Next[6]  P[0] ~ P[6]:A A C A A C A  4
Next[7]  P[0] ~ P[7]:A A C A A C A A  5
Next[8]  P[0] ~ P[8]:A A C A A C A A A  2
Next[9]  P[0] ~ P[9]:A A C A A C A A A A 2

模式串p共有p.size()个从0开始的子串,对于每个子串,要计算最大相同真前后缀长度,可以从长度1开始枚举,比较前后缀是否相同,整体时间复杂度是n^2的。

Next数组的递推求法:

递推原理:

如果Next[j]已经求出,要求Next[j+1]

那么当p[j+1]==p[Next[j]]时,显然Next[j+1] = Next[j]+1,

当p[j+1]!=p[Next[j]]时,j+1应该跟Next[Next[j]-1]进行比较,如下图描述:

递推实现:

初始时,Next[0] = 0,因为一个字符的子串没有真前后缀,所以最长相同真前后缀长度是0。

采用双指针i = 1,j = 0均遍历p,

i代表要计算的p的子串最长后缀结尾位置,即要计算Next[i],Next[0]已经初始化,从1开始,

j代表要计算的p的子串最长前缀结尾位置,

遍历i,

如果p[i] != p[j],j同样也要跳到Next[j-1]继续和p[i]比较,直到相等或者j==0。

如果p[i] == p[j],则j++,Next[i] = j,

计算Next的核心代码为:

for(int i = 1, j = 0; i < plen; i++)
{
    while(j && p[i] != p[j]) j = Next[j - 1];
    if(p[i] == p[j]) j++;
    Next[i] = j;
}

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

string s, p;
int Next[N];

int main()
{
    cin >> s >> p;
    int slen = s.size();
    int plen = p.size();

    //计算Next数组
    for(int i = 1, j = 0; i < plen; i++)
    {
        while(j && p[i] != p[j]) j = Next[j - 1];
        if(p[i] == p[j]) j++;
        Next[i] = j;
    }

    //执行kmp算法
    for(int i = 0, j = 0; i < slen; i++)
    {
        while(j && s[i] != p[j]) j = Next[j - 1];
        if(s[i] == p[j]) j++;
        if(j == plen)
        {
            cout << i - plen + 1 + 1 << endl; //出现的位置是字符串的下标再加1
            j = Next[j - 1];
        }
    }

    //输出Next数组
    for(int i = 0; i < p.size(); i++) cout << Next[i] << " ";

    return 0;
}

 

标签:子串,后缀,洛谷题,++,Next,int,KMP,P3375,size
From: https://www.cnblogs.com/jcwy/p/18454220

相关文章

  • KMP算法
    引言之前在打ACM竞赛时就学过一些字符串相关的算法,其中就包括KMP。但是面向竞赛的KMP算法和面向408的KMP算法在一些概念和实现细节上有细微差异,所以特意写了这篇文章对408中的KMP算法做出总结字符串的前缀、后缀和部分匹配指前缀指除了最后一个字符以外,字符串的所有头部子串;后......
  • 洛谷题单指南-分治与倍增-P6648 [CCC2019] Triangle: The Data Structure
    原题链接:https://www.luogu.com.cn/problem/P6648题意解读:在一个n行的数字三角形中,求所有边长为k的正三角形最大值之和。解题思路:1、枚举法枚举每一个边长为k的三角形,在其中求max,然后累加,n最多3000,时间复杂度是n^4,显然超时。2、倍增和ST思想此题非常类似于RMQ问题,也就是求区......
  • 8592 KMP算法
    首先,我们需要理解KMP算法的基本思想。KMP算法是一种改进的字符串匹配算法,它的主要思想是利用已经部分匹配的这个有效信息,使得后续的匹配中,尽量减少字符串的回溯,提高匹配效率。KMP算法的关键在于通过一个next数组,保存模式串中前后缀的最长的共有元素的长度。当模式串中的字符......
  • 洛谷题单指南-分治与倍增-P4155 [SCOI2015] 国旗计划
    原题链接:https://www.luogu.com.cn/problem/P4155题意解读:在m个点的环上,有n个区间,且各个区间之间没有包含关系,计算从每个区间开始,最少要多少个区间能覆盖环上所有m个点。解题思路:本质上是一个区间覆盖问题!1、破环成链由于题目中是一个环,对于环的问题,在区间DP中介绍过,经典处理......
  • 字符串从入门到退竞(2)——KMP 算法
    约定在文字描述中字符串下标从\(1\)开始,代码中从\(0\)开始。前缀函数对于长\(n\)的字符串\(S\),其前缀函数是一个长\(n\)的数组(数列)\(\pi\),定义如下:若\(S[1..i]\)有相等的真前缀和真后缀(称之为border),\(\pi[i]\)为其长度的最大值;若不存在,\(\pi[i]=0\)。字符串的......
  • 洛谷题单指南-分治与倍增-P3517 [POI2011] WYK-Plot
    原题链接:https://www.luogu.com.cn/problem/P3517题意解读:有n个连续的点p1,p2,...,pn,将这n个点分成不超过m堆,每堆点连续,每一堆都缩成一个点qi,要使得原来的点p1~ps距离qi的最大值最小(最相似),求这个相似度,并计算一共分成几堆,以及每堆缩到的点qi的坐标。解题思路:要使得若干点缩到一......
  • 【算法】C++KMP算法的简洁实现
    目录简介next数组匹配完整代码简介对于朴素的字符串匹配算法,如果想在主串中寻找到第一次出现子串的位置,需要依次枚举主串中的每一个位置作为起始位置进行匹配尝试,如果主串中存在许多与子串相似结构的部分,那么朴素算法会进行大量的无用枚举,时间复杂度非常之高。KMP算法......
  • 洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog
    原题链接:https://www.luogu.com.cn/problem/P3509题意解读:n个点,每个点上有一只青蛙每次跳到距离自己第k近的点,m次之后跳到哪个点。解题思路:1、计算距离每个点第k近的点,存入ne[N]给定一个点i,距离i第k近的点一定在长度为k+1个点的窗口内,窗口包括i并且,第k近的点只能是左端点或者......
  • 923kmp 01背包
    kmp遍历一次主串匹配子串求next数组看前后缀相同的个数不匹配时根据next的值移动p3375点击查看代码voidgetNext(strings,intnextt[]){intj=0;nextt[0]=0;for(inti=1;i<s.size();i++){while(j>0&&s[i]!=s[j]){......
  • KMP算法的实现
             这是C++算法基础-数据结构专栏的第二十六篇文章,专栏详情请见此处。引入     KMP算法是一种可以快速查找某一字符串在一个文本中的所有出现的算法。        下面我们就来讲KMP算法的实现。定义        Knuth–Morris–Pratt算......