基础字符串

KMP & Manacher

KMP

KMP(Knuth - Morris - Pratt)算法是一种能在$\Theta(n + m)$时间内进行字符串匹配的算法。

其基本思想是构造一个Next[]数组,表示在i位置匹配串失配时跳转到Next[i]

举例如下:

有字符串A : a a a a b a b a b b a

字符串B : a b a b b

约定第一个字符序号为1。

然后显然A在1 2 3处不匹配。

Index 4 5 6 7 8 9 10 11
A a b a b a b b a
B a b a b b

当B以4为起点,匹配到8时失配。这时如果从5开始重新匹配显然复杂度不佳。

这时我们观察到6 7处的字符与4 5处相同,即我们可以从6开始匹配。

Index 4 5 6 7 8 9 10 11
A a b a b a b b a
B a b a b b

此时A与B匹配。

这个例子给我们以启示:如果根据匹配串的特点,当在某一点失配时直接跳到已经被部分匹配的区域继续匹配,即可以得到高效算法。

如何构造Next[]?

根据算法思路,我们要拿匹配串匹配自己。Next[1]显然为0。所以我们从2开始推:

上例中B的Next值如下:

Index 1 2 3 4 5
B a b a b b
Next 0 0 1 2 0

最后给出板子(Luogu P3375):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstring>
#define N 1000010
char S[N],T[N];int next[N],s,t;
inline build_next()
{
for(int i = 2,j = 0;i <= t;i++)
{
while(j && T[i] != T[j + 1]) j = next[j];
if(T[j + 1] == T[i])j++;
next[i] = j;
}
}
int main()
{
scanf("%s",S + 1);scanf("%s",T + 1);s = strlen(S + 1),t = strlen(T + 1);
build_next();
for(int i = 1,j = 0;i <= s;i++)
{
while(j && S[i] != T[j + 1]) j = next[j];
if(T[j + 1] == S[i])j++;
if(j == t){printf("%d\n",i - t + 1);j = next[j];}
}
for(int i = 1;i <= t;i++) printf("%d%c",next[i]," \n"[i == t]);
return 0;
}

Manacher

Manacher算法用来在$\Theta(n)$时间内计算字符串的最长回文串。

首先由于长度为偶数的字符串的对称中心不在字符上,不方便研究,所以我们在字符串开头,结尾,以及字符之间添加不在字符表内的字符,如’#’。这样就可以转化为研究奇数长度的回文串了。

我们可以用p[i]表示以i为对称轴的回文串长度,当我们要计算p[i]时,我们可以记录下之前的回文串到达的最右端距离mx和最右回文串的对称轴位置id。

$mx \leq i$时显然只能暴力搞。

否则如图:

可得到$p_i = min(p_{2id - i},mx - i) \ (mx > i)$ 。

板子(Luogu P3805):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 41001100
char S[N],T[(N << 1) + 20];int p[N],s,t,mx = 0,id = 0,ml = 0;
int main()
{
scanf("%s",S + 1);
s = strlen(S + 1);
T[0] = '$',T[2 * s + 1] = '#';for(int i = 1;i <= s;i++) T[i * 2 - 1] = '#',T[i * 2] = S[i];t = 2 * s + 1;
for(int i = 1;i <= t;i++)
{
if(mx > i) p[i] = std::min(p[id * 2 - i],mx - i);
else p[i] = 1;
while(T[i + p[i]] == T[i - p[i]])p[i]++;
if(p[i] + i > mx)mx = p[i] + i,id = i;
ml = std::max(ml,p[i] - 1);
}
printf("%d\n",ml);
return 0;
}