首页 > 其他分享 >KMP&exKMP

KMP&exKMP

时间:2024-08-10 11:39:45浏览次数:12  
标签:exKMP ... 前缀 计算 数组 KMP 字符串

(之前学的一些东西都没打笔记,给忘的差不多了。从这个开始要记得写笔记了。)

注意事项:所有的字符串的下标从1开始。

KMP

对于一个字符串 s ,定义它的前缀数组a,其中a[i]表示子串s[1...i]前缀与后缀相同的最大长度(不包括串自身)。

对于朴素的算法,自然是n^2的暴力。考虑利用前面位置的值来计算当前位置的值。

设当前位置为i。发现a[i]<=a[i-1]+1,同时发现当s[i]=s[a[i-1]+1]时,a[i]=a[i-1]+1。

那么如果不相等呢?

我们需要找到一个更小的j,考虑j的取值可能在哪里。我们需要找到一段满足s[i-j+1...i]=s[1...j]的,才能快速得出当前答案。

发现a[a[i-1]]的值满足这一性质(参考下图)。所以我们可以不断递归,直至j=0。(要注意,j=0时有可能a[i]=1。)

用途:

我们处理出来这个数组有什么用呢?

首先当然是匹配。假设当前有一个串S,一个模式P,求P在S的哪些位置能匹配?

我们将两个字符串连接起来:P+‘#’+S(‘#’表示一个在两个串中都不出现的字符)。然后计算出 |P|+2~|P|+|S|+1 的前缀数组。根据前缀数组的性质,当 a[i]=|P| 时,P在S中出现了一个匹配。

计算一个串中,本质不同的串的数量。

考虑每次加入一个字符,计算产生了多少个不同的串。从末尾加入一个字符,然后设当前串的反串为S'。处理出每个位置的前缀数组。整个序列的前缀数组的最大值即为增加的本质相同的串。

计算每个前缀的出现次数。

容易,计算有多少个前缀数组的值是相同的就行了。

exKMP

exKMP,也叫 Z 函数。定义字符串S的Z函数为:z[i]表示字符串S与以i开头的后缀的LCP。

考虑字符串中常用的处理方法:利用前面已经求得的数据计算当前的数据。

我们维护一个l、r,表示与S的某个前缀相同的、右端点最右的区间,其实就是S[i...i+z[i]]。这里我们钦定z[1]=0,从第2个数开始计算。

设当前的位置为i。当i<r时,由于S[i...r]=S[i-l+1...r-l+1],所以考虑通过z[i-l+1]求z[i]。若z[i-l+1]<r-i+1,则z[i]=z[i-l+1]。因为如果z[i]>z[i-l+1],那么根据l与r的定义,S[z[i-l+1]+1]=S[i-l+1+1],即z[i-l+1]会更大。若z[i-l+1]≥r-i+1,那么我们将z[i]暂时设为r-i+1,然后暴力延伸。

当i≥r时,将z[i]设为0,然后暴力延伸。记得计算完一个z[i]后,要更新l、r。

考虑时间复杂度的正确性。每一次延伸,如果没有暴力延伸,则时间复杂度为O(1);如果暴力延伸,则r一定会改变,又由于r最大为n,所以最多扩展|S|位。总的复杂度为O(|S|)。

应用:

同KMP一样,可以匹配,可以计算本质不同的子串数量。

计算一个串的最小整周期,即对于一个串S,求一个长度最小的串t,使得t可以通过若干次复制构成S。算出位置i的z[i]后,若i-1为n的因数且z[i]+i-1=|S|,则S[1...i-1]为S的整周期。

标签:exKMP,...,前缀,计算,数组,KMP,字符串
From: https://www.cnblogs.com/Cyanwind/p/18352111

相关文章

  • kmp算法(c++)
    kmp算法的简单介绍从主串中快速找到与要找的串的相同位置如果使用暴力算法去求解这个问题,时间复杂度为O(i*j)=>很大kmp算法则是对这类问题的优化因整理过于麻烦,,详细的介绍可以参照这篇博客,,花时间看完就明白了,写的很棒!!!kmp算法详细介绍下面是自己学习的一些注意的地......
  • kmp算法模板
    模板//pi代表前缀函数 //pi[i]:s[0~i]的最长匹配真前后缀长度 vecotr<int>pi(str.size()); //求前缀函数 for(inti=1;i<str.size();i++){ intlen=pi[i-1];//前一个值的pilen是我们想要找到的一个长度值 while(len!=0&&str[i]!=str[len]){//不匹配时,......
  • KMP 与 Z 函数拓展
    【失配树:KMP拓展】先KMP一遍。然后对\(0\simn\)建立一棵树:\(nxt[i]\)作为\(i\)的父结点。则最长公共border就是这棵树上的LCA对应的长度。border:若\(a\)既是\(s\)的前缀又是\(s\)的后缀,则\(a\)是\(s\)的border。周期:若\(s\)以\(p\)为周期,则\(s[......
  • KMP算法
     ......
  • KMP算法
    写在前面喜报:听了四遍都没学懂的KMP算法,终于在gyy大佬的耐心讲解下搞懂了,大佬orz!!!正文kmp算法本质上就是对模式串(要匹配的子串两个串中短的那个)中很多重复的前缀和后缀索引起来,使得在一个地方失配了也不要紧,不用重新来的算法(看不懂不要紧)下面我们就来详细介绍一下kmp的几个......
  • KMP学习笔记
    KMP一种字符串单模匹配算法。原理当模式串\(s\)与文本串\(t\)进行匹配时,容易想到的一种朴素做法就是将模式串的第一位与文本串的每一位进行试配。但是这样效率过低,容易被数据卡成\(O(n^2)\)。KMP单模匹配算法引入了一个失配数组border。定义一个字符串的border为一......
  • KMP 算法学习笔记
    问题引入给出两个字符串\(s1\)和\(s2\),求出\(s2\)在\(s1\)中所有出现的位置(出现指\(s1\)中存在子串与\(s2\)完全相同)。朴素暴力不详细介绍,容易发现时间复杂度不优秀。KMP算法思想在朴素暴力中我们可以发现有很多匹配是不需要再次从头开始重新匹配的,举个例子:ABA......
  • 重学 KMP 小记
    重学KMP小记前言KMP这个东西赛时用到的几率很小(虽然圣人说概率不小、也不是很大),但是如果一旦考字符串类的题又极可能考匹配问题。当时掌握得也是一知半解,所以现在来重学来了。情境引入现实中我们会遇到类似的问题:给你一篇报道,让你找一找这篇报道中有没有出现某个人的名字......
  • 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}\)短小精悍,极其精简,确实难懂,所以很......