KMP，字符串算法万恶的源头

默认下文所有字符串的下标从

1

开始。下文用

s[l\dots r]

表示

s_l,s_{l+1},\dots,s_r

顺次拼接出的字符串，即

s

在下标区间

[l,r]

内的子串。

学会 KMP，要先学会求 border。

border 是一个字符串

s

对应的长度为

|s|

的数组。对

\text{border}_i

的定义为：在字符串

t=s[1\dots i]

中，使得

t[1\dots v]=t[i-v+1\dots i]

的最大可能值

v

（需要满足

v\neq i

）。

其求法为：假设当前已经求出了

\text{border}_1,\text{border}_2,\dots,\text{border}_{i-1}

，需要求

\text{border}_i

，则定义一个值

tp

，初始

tp=\text{border}_{i-1}

，进行下面的操作：

如果 $s_{tp+1}=s_i$ ，则 $\text{border}_i$ 就是 $tp$ ，赋值并结束操作。
反之，让 $tp\leftarrow \text{border}_{tp}$ 。
如果此时 $tp=0$ ，则 $\text{border}_i=0$ ，结束操作，否则回到第一步继续操作。

其实就是一个让

s[1\dots tp+1]

与

s[i-tp\dots i]

不断匹配的过程，这里的

tp

满足

s[1\dots tp]=s[i-tp\dots i-1]

。复杂度~~感性理解~~就是线性的。

至此，border 已经求完了。

代码

CPP

fo(i,1,n){
    int tp=border[i-1];
    while (tp&&s[i]!=s[tp+1])
        tp=border[tp];
    if (s[i]==s[tp+1])
        tp++;
    border[i]=tp*(i>1);
}

在字符串

s

中匹配

t

字符串的做法是类似的，如果

s_{i+1}

与

t_{tp+1}

匹配，就

tp\leftarrow tp+1

；否则就让

tp\leftarrow \text{border}_{tp}

，继续匹配。复杂度也是线性的。

KMP 算法可以用来优化 dp。比如 P3082 这个题，在求出 border 之后，dp 的过程相当于 KMP 匹配字符串的算法，可以优化时间复杂度。

KMP，字符串算法万恶的源头

文章操作

相关推荐

评论

KMP，字符串算法万恶的源头