schtonn

schtonn

0%

拓展 KMP

Posted on Edited on Valine:

前置知识

字符串基础操作；强烈建议先学习 KMP 和 manacher，对理解有很大帮助。

引入

假设模式串是 pat，文本串是 txt。

拓展 KMP，有时也叫 Z 函数，是求 pat 和 txt 的（所有）后缀的最大公共前缀长度，用 z[i] 表示。

预处理

拓展 KMP 和 KMP 一样，都是预处理一个数组。

KMP 预处理的数组是这样的： KMP

拓展 KMP 预处理的数组是这样的： exKMP

如图，拓展 KMP 处理的实际上是模式串自身和它的所有后缀的最大公共前缀长度。

假设模式串是 aabaaba，那么我们一位一位地向前暴力匹配，最终得出的结果就是 x104101（第一位没有意义）。我们称这个预处理数组为 extend[]。

过程

拓展 KMP 的思路与 manacher 很相类似，都是先通过朴素算法得出既有结论，再通过既有结论省去不需要的判断。

同样的，我们维护 r 和 s 表示当前匹配到的区间右边界最大值和那个区间的起始位置。

迭代 i，计算 z[i]： - 如果 i>r： 运行朴素算法，找到向右匹配前缀的最大值。 - 如果i<=r： 因为当前位置在之前匹配过的一个区间内，说明这个由 s 开始的区间和模式串的某个前缀是完全相等的，那么我们就可以把前面预处理的 extend[] 拿过来，认为 z[i] 至少为 extend[i-s] 和 r-i 中的最大值。

我们假设文本串是 aaaabaabaabaa；

\[\mathtt{aaaabaabaabaa}\]

首先朴素算法匹配到 z[1]=2，那么就出现了长度为 2 的区间，r 也变成了 2；

\[\begin{array}{clr}\mathtt{aaaabaabaabaa}\\\hspace{-6.3em}\uparrow\\\mathtt{2000000000000}\end{array}\]

接着根据 extend[2-1] 可以看出 z[2] 至少为 1，继续朴素匹配发现 z[2]=2，r=3；

\[\begin{array}{clr}\mathtt{aaaabaabaabaa}\\\hspace{-5.2em}\uparrow\\\mathtt{2200000000000}\end{array}\]

z[3] 匹配得出 7，同理接下来的 a，b，a 至少为 1，0，4；

\[\begin{array}{clr}\mathtt{aaaabaabaabaa}\\\hspace{-4.1em}\uparrow\\\mathtt{2270000000000}\end{array}\]

z[6] 再一次得出 7，接下来依然至少为1，0，4；

\[\begin{array}{clr}\mathtt{aaaabaabaabaa}\\\hspace{-1em}\uparrow\\\mathtt{2271070000000}\end{array}\]

z[9] 碰到了边界，得出 5。很快我们可以看到，z[12] 的 a 由于碰到边界，至少为 2 而不是 4。

\[\begin{array}{clr}\mathtt{aaaabaabaabaa}\\\hspace{3.8em}\uparrow\hspace{1.2em}\uparrow\\\mathtt{2271071051021}\end{array}\]

代码

1
2
3
4
5
6
#include "bits/stdc++.h"
using namespace std;
int main(){
    cout<<"not yet"<<endl;
    return 0;
}