首页 > 其他分享 >重学 KMP 小记

重学 KMP 小记

时间:2024-08-03 22:20:59浏览次数:13  
标签:子串 int next MAXN str KMP 小记

重学 KMP 小记

前言

KMP 这个东西赛时用到的几率很小(虽然圣人说概率不小、也不是很大),但是如果一旦考字符串类的题又极可能考匹配问题。当时掌握得也是一知半解,所以现在来重学来了。

情境引入

现实中我们会遇到类似的问题:

给你一篇报道,让你找一找这篇报道中有没有出现某个人的名字。

形式化地,可以说:

给你文本串 \(S\),和模式串 \(T\),判断 \(T\) 是否为 \(S\) 的子串。

这个问题我们暴力地想,可以用两个指针 \(i\),\(j\) 分别表明现在匹配到 \(S\),\(T\) 的哪个位置了(\(0\le i< len_S\),\(0\leq j<len_T\))。如果 \(S_i\neq T_j\),则 \(i\leftarrow i-j+1\)、\(j\leftarrow 0\)。相当于是推翻重来。

有没有优美一点的算法呢?答案是有的,就是我们的主角——KMP。

算法概要

我们在暴力的时候,如果一旦失配,模式串的指针 \(j\) 就又从头开始,这显然是非常浪费的。所以我们如果想降低时间复杂度,就要从这里入手。

首先我们定义一个数组 \(next_i\),其满足:\(S_{[0,next_i-1]}=S_{[i-next_i,i]}\)。\(S_{[l,r]}\) 表示 \(S_l,S_{l+1},\dots,S_{r}\) 组成的子串。当然这个 \(next_i\) 有很多种情况,我们储存的是子串最长的情况。说白了这两部分子串就是 \(S_{[0,i]}\) 的最长公共前后缀。

特别地,\(next_0=-1\)。

接下来就可以引入 KMP 了,算法流程如下:

  1. 如果 \(S_i\) 与 \(T_{j+1}\) 匹配成功,即相同,就 \(i\leftarrow i+1\),\(j\leftarrow j+1\),继续匹配。
  2. 如果失配,则令 \(i\) 不动,\(j\leftarrow next_j\)。这意味着 \(S\) 不变,将整个 \(T\) 向右移动了 \(j-next_j\) 位。这个值肯定是大于等于 \(1\) 的。

这样就没了。

现在来分析一下这个 KMP 是怎么减少浪费的。

当 \(T\) 匹配到 \(j\) 位时,说明前面都是和 \(S\) 相同的。如果此时失配了,暴力的思想是相当于直接把 \(T\) 向右平移一位,然后重新比较。这样显然没有前途。KMP 是怎么做的呢?KMP 的思想是:“既然我这个 \(T_{[0,j]}\) 里可能有公共前后缀,如果有的话,为什么我不直接把 \(T\) 向右平移至这个最长公共前后缀相同的部分呢?”。

画个草图理解一下:

图中蓝色的部分都相同。

如何预处理 \(next_i\) 数组

考虑递推。现假设 \(next_{[0,i-1]}\) 的元素都已求出。

算法过程就很简单了:

  1. 如果 str[i]==str[next[i-1]+1],则 next[i]=next[i-1]+1
  2. 否则判断 str[i]str[next[next[i-1]]+1] 是否相等。
  3. 再否则,判断 str[i]str[next[next[next[i-1]]]+1] 是否相等。
  4. 回环往复,直至相等或 \(next\) 的值为 \(0\) 为止。
void getnxt()
{
	int j=0;
	for(int i=2;i<=m;i++)
	{
		while(j&&b[j+1]!=b[i])
			j=nxt[j];
		if(b[j+1]==b[i])
			j++;
		nxt[i]=j;
	}
}

例题展现

P3375 【模板】KMP

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

#define int long long

const int MAXN=1e6+5;

int n,m;
char a[MAXN];
char b[MAXN];
int nxt[MAXN];

void getnxt()
{
	int j=0;
	for(int i=2;i<=m;i++)
	{
		while(j&&b[j+1]!=b[i])
			j=nxt[j];
		if(b[j+1]==b[i])
			j++;
		nxt[i]=j;
	}
}

void kmp()
{
	for(int i=1,j=0;i<=n;i++)
	{
		while(j&&a[i]!=b[j+1])
			j=nxt[j];
		if(b[j+1]==a[i])
			j++;
		if(j==m)
		{
			printf("%lld\n",i-m+1);
			j=nxt[j];
		}
	}
}

signed main()
{
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1),m=strlen(b+1);
	getnxt();
	kmp();
	for(int i=1;i<=m;i++)
		printf("%lld ",nxt[i]);
	return 0;
}

标签:子串,int,next,MAXN,str,KMP,小记
From: https://www.cnblogs.com/holmes-wang/p/18341183

相关文章

  • KMP
    KMP第114514遍重新学。这个算法的作用求出前缀函数\(\pi\),一种应用才是字符串匹配。真前缀:是前缀但不是其本身,即最长为\(s[1\dotsn-1]\)。前缀函数:一般地,前缀函数\(\pi[i]\)表示子串\(s[0\dotsi]\)最长的相等的真前缀与真后缀的长度,代码中我们一般写作\(nxt[i]\)......
  • 算法·理论:KMP 笔记
    \(\text{KMP}\)笔记!上次比赛,出题人出了一个\(\text{KMP}\)模板,我敲了个\(\text{SAM}\)跑了,但是学长给的好题中又有很多\(\text{KMP}\),于是滚回来恶补字符串基本算法。\(\text{KMP}\)是上个寒假学的,为什么最近才完全理解,但\(\text{KMP}\)短小精悍,极其精简,确实难懂,所以很......
  • 剪花布条(KMP)
    题目描述一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案。对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢?输入描述输入中含有一些数据,分别是成对出现的花布条和小饰条,其布条都是用可见ASCII字符表示的,可见的ASCII字符有多少个......
  • 学linux小记(1)
    1.SELinux上下文就是所谓的标签由SElinux分配2.setenforce0是更改SELinux的模式一般0是改到Permissive模式 1是改到enforcing 3.对于定义SELinux文件上下文规则时 采用semanagefcontext命令举例semanagefcontext-a-t你写的上下文  '/某个目录或文件+(/.......
  • 【学习笔记】KMP
    【学习笔记】KMP因为字符串对我太抽象了,所以只能以水的心态写这个KMP。感觉考到字符串的题肯定要崩。以下均规定字符串\(S\)以下标0开头。前缀函数:给定一个长度为\(n\)的字符串\(S\),其前缀函数被定义为一个长度为\(n\)的数组\(\pi\)。简单来说\(\pi[i]\)就是,子......
  • NDM 小记
    NDM1、什么是ndmNeatDownloadManager(简称NDM)是一款免费且轻量级的多线程下载工具,支持Windows和macOS操作系统。这款软件的特点在于它能够有效地提升网络下载速度,并且具有简单的用户界面,易于上手。最重要的是:体积小且免费!!!2、安装ndm下载地址:https://www.neatd......
  • 牛客SQL练习小记
    牛客SQL练习总结计算新用户的次日留存率太失败了!!一步一个坎,面对这个问题没有完整的思路,想到一半就无法继续了,只能看大佬们的sql获得启发--思路--这道题关键的两点,一个是标志出新用户,这个可以通过窗口函数min,根据uid分组,计算出首次登录时间--另一个就是二次登陆日期,这个......
  • 多项式基础内容小记
    0.基础知识:关于多项式的定义:多项式:一个形如\(f(x)=\sum_{i=0}^na_ix^i\)的有限和式被称为多项式。系数:多项式第\(i\)项的系数在上面就表示为\(a_i\)。度(次数):多项式中最高次数的项的次数就被称为该多项式的度,也称次数。多项式表示法:多项式有两种表示法:......
  • 正则表达式小记
    转义字符在正则表达式中,某些字符具有特殊的含义,它们被称为元字符或特殊字符。当你希望这些特殊字符按照字面意义匹配文本时,就需要使用转义字符(通常是反斜杠\)来“取消”它们的特殊含义。以下是正则表达式中需要转义的常见特殊字符:反斜杠用于转义其他特殊字符或创建预定义字符......
  • KMP1(字符串基本概念,KMP算法和简单应用)
    KMP1(字符串基本概念,KMP算法和简单应用)基础定义字符串\(S\):无特殊说明,字符串仅由26个小写字母\('a'-'z'\)构成,并用大写字母表示一个字符串。\(|S|\):表示一个字符串的长度\(S[i]\):表示字符串\(S\)第\(i\)个位置的字母,下标从\(1\)开始。子串\(S[l,r]\):表示......