扩展KMP模板

概述

参考资料:

刘雅琼PPT讲解
kuangbin的博客

给出模板串A和子串B,长度分别为$lenA$和$lenB$,要求在线性时间内,对于每个$A[i]$$(0 <= i < lenA)$

求出$A[i..lenA-1]$ 与B的最长公共前缀长度,记为$ex[i]$(或者说,$ex[i]$为满足$A[i..i+z-1]==B[0..z-1]$的最大的z值)。

扩展KMP可以用来解决很多字符串问题,如求一个字符串的最长回文子串和最长重复子串。

(1)头文件

1
2
3
4
5
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000010;
int Next[MAXN];
int extend[MAXN];

(2)EXKMP

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void EKMP(char s[],char t[])//s为主串,t为模板串
{
int i,j,p,L;
int slen = strlen(s);
int tlen = strlen(t);
Next[0] = tlen;
j = 0;
while(j+1 < tlen && t[j] == t[j+1])
j++;
Next[1] = j;

int a = 1;
for(i = 2;i < tlen;i++)
{
p = Next[a]+a-1;
L = Next[i-a];
if(i+L<p+1)
Next[i]=L;
else
{
j=max(0,p-i+1);
while(i+j < tlen && t[i+j] == t[j])
j++;
Next[i] = j;
a = i;
}
}

j = 0;
while(j < slen && j < tlen && s[j] == t[j])j++;
extend[0] = j;
a = 0;
for(i = 1;i < slen;i++)
{
p = extend[a]+a-1;
L = Next[i-a];
if(L+i < p+1)
extend[i] = L;
else
{
j = max(0,p-i+1);
while(i+j<slen && j < tlen && s[i+j] == t[j])
j++;
extend[i] = j;
a = i;
}
}
}

补充

  • $extend[i]$表示原串以第$i$开始与模式串的前缀的最长匹配

经典题目:

HDU3613

HDU 3613 Best Reward(扩展KMP:回文判断) - CSDN博客