【OI之路】10字符串-3ExKMP算法

一句精辟的话:字符串相关算法就是用来偷懒的 ——scy
更详细地解释:Manacher、莫队、fft、后缀数组、exkmp等各种算法,本质上都是尽量地利用子信息、残留信息
本文思路和图片大致来自于师兄cys大佬的论文
本文会用相同颜色分别表示图片中某段的相等性

一、定义

KMP:$str(1,nxt[i])=str(i-nxt[i]+1,i)$
exKMP:$str(1,ext[i])=str(i,i+ext[i]-1)$
然后接下来的过程中,思路和manacher是灰常类似的,各种分类讨论继承

二、求ext数组

$ext[1]=lenb$(显而易见)
因为ext[1]这个是具有一定性,所以我们基本把这东西废掉……
那么我们就直接从ext[2]开始求。

A. k表示在当前搜索过的范围以内,rx=k+ext[k]-1最远(与manacher很像)
str(1,ext[k])=str(k,rx)
因为$rx=k+ext[k]-1$,又得:$ext[k]=rx-k+1$
代换变成:str(1,rx-k+1)=str(k,rx)
因为现在要求ext[i],截取str(i-k+1,rx-k+1)=str(i,rx)

B. 设$L=ext[i-k+1]$,又得:str(1,L)=str(i-k+1,i-k+L)

接下来尝试合并。因为L的不定性,需要考虑$i-k+L$和$rx-k+1$的大小

(1)i-k+L<rx-k+1
因为str(1,L)=str(i-k+1,i-k+L)str(i-k+1,rx-k+1)=str(i,rx)
所以在str(i,rx)str(i,i+L-1)=str(1,L)

因为str(i-k+1,rx-k+1)=str(i,rx),得:
str[i-k+L+1]=str[i+L]
而因为ext[i-k+1]的定义,所以str[L+1]!=str[i-k+L+1]
得:str[i+L]!=str[L+1],那么$ext[i]=L$
小总结:主要利用【$i-k+L+1$已经扫描过】

(2)i-k+L>=rx-k+1

str(1,L)=str(i-k+1,i-k+L)
所以str(1,rx-i+1)=str(i-k+1,rx-k+1)
因为ext[k]的意义,所以str[rx+1]!=str[rx-k+2]
又有可能str[rx-i+2]!=str[rx-k+2](与rx-i+1与L的大小关系有关),那么就会得到:str[rx-i+2]!=str[rx+1],所以$ext[i]\geq rx-i+1\geq ext[i-k+1]$

总结:
当$i-k+L<rx-k+1$,$ext[i]=L$
当$i-k+L\geq rx-k+1$,$ext[i]\geq ext[i-k+1]$

三、用ext数组

好啦我们要开始匹配A串(母串)和B串了
定义ex数组,$B(1,ex[i])=A(i,i+ex[i]-1)$
即A中每个后缀与B的最长公共前缀长度
某种理解:
将i-k+1看作i的对应点,将串B和串A放在同一条线上,
前面用ext,后面用ex,则L为ext[i的对应点]

四、总结

让我们再次对比一下kmp与exkmp
KMP:$str(1,nxt[i])=str(i-nxt[i]+1,i)$
exKMP:$str(1,ext[i])=str(i,i+ext[i]-1)$
对于kmp,当i向后时,利用前面的信息是灰常简单的,一个比较即可;
而对于exkmp,前后的i之间并没有较紧密的联系,需要较复杂地分情况讨论

那么这个“牺牲”为我们带来了什么呢?
如ex一样的字符串局部信息,并且能够有从i开始的信息。

五、例题

最长共同前缀长度
回文串
字符串的相似度

六、练习题

Tag-exkmp

七、一张图快速复习exkmp

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/4360.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%