扩展KMP问题

缘起

【1】中我们已经分析了KMP算法. 下面考虑扩展KMP问题.

1
2
给定母串T，和子串p, 0索引不用于存储数据, 定义n=|T|（strlen(T)）, m=|p|，extend[i]=T[i..n]与p的最长公共前缀长度(LCP),即extend[i]=LCP(T[i,...,n], p[1,...,m])
请在线性的时间复杂度内，求出所有的extend[1..n].

分析

本篇文章先介绍上述扩展KMP算法的原理, 后续几篇文章再介绍扩展KMP算法的应用.

首先，为什么该问题叫做扩展KMP问题呢? 如果我们发现extend[k]=m for some k的话，则就知道p在T中出现了, 这不就是KMP算法想解决的问题么? 所以扩展KMP算法的目的虽然是在线性时间内求解 extend[1,…,n], 但是顺便将KMP问题解决了. 所以”扩展KMP问（算）题（法）”由此得名. 而且至少从KMP的角度上来说，我们的扩展KMP问题是有意义的——它从不同的视角解决了KMP问题.

下面我们来求解扩展KMP问题. 算法是DP，假设我们求解出来了extend[1,..,k], 要求 extend[k+1], 我们假设

1
extend[a]+a-1 = max{extend[1]+1-1,..,extend[k]+k-1}, 1<=a<=k

也就是a是使得 extend[a]+a-1是{extend[1]+1-1,..,extend[k]+k-1}中取得最值的那个下标.

其中extend[i]+i-1的意义是T[i,…,n]和p[1,…,m]的LCP，即

1
LCP(T[i,...,n], p[1,...,m]) = extend[i], 1<=i<=n

那么extend[k+1]等于什么呢? 将至今为止的分析列为下图

根据extend定义，我们已经知道了

1
T[a,...,a+extend[a]-1] = p[1,...,extend[a]]····································（1）

然后我们要思考最大的x满足下式

1
T[k+1,....,k+x]=p[1,...,x]

根据式（1），我们知道

1
T[k+1,...,a+extend[a]-1]=p[k-a+2,...,extend[a]]································（2）

所以如果我们令（先不管next[i]的求解，假设我们已经求出来了）

1
next[i] = LCP(p[1,...,m], p[i,..,m])

的话，则据此我们有（注意，我们仅仅需要用到next[2,…], 因为next[1]显然=m, 也是不需要用到的）

1
p[k-a+2,...., next[k-a+2]+(k-a+1)] = p[1,...,next[k-a+2]]·························(3)

所以 (3)+(2), 我们可以知道

1
2
如果 next[k-a+2]+(k-a+1)<extend[a], 即k+next[k-a+2]<extend[a]+a-1, 即（3）的左边被（2）的右边盖住了，则
T[k+1,....,next[k-a+2]+k] = p[1,...,next[k-a+2]]

即 extend[k+1]=next[k-a+2]. 注意，不可能extend[k+1]再大了，不然的话，与next[k-a+2]的定义相矛盾. 则

1
extend[k+1]=next[k-a+2]

并且, a不会变化，继而 next[a]+a-1也不会发生变化.

反之

1
2
如果next[k-a+2]+(k-a+1)>=extend[a],即k+next[k-a+2]>=extend[a]+a-1, 则(3)的左边包含了(2)的右边，则
T[k+1,...,a+extend[a]-1]=p[1,...,a+extend[a]-k-1]

则我们只需要从T[a+extend[a]] （注意，a+exntend[a]>=k）开始与p[a+extend[a]-k]比较即可. 直至失配为止, 假设直至 T[x]=p[y]（T[x+1]!=p[y+1]）, 即 x-(a+extend[a])=y-(a+extend[a]-k) ，即x=y+k. 则

extend[k+1]=x-k, 然后我们比较一下 (k+1)+extend[k+1]-1和a+extend[a]-1,看看是不是前者比后者大, 如果是的话，则更新a为k+1.

至此，除了next数组的制作之外，算法的其它都好了. 下面我们来讨论一下next数组的制作.

我们先来回顾一下next数组的定义

1
next[i]=LCP(p[i,...m], p[1,...,m])

wait wait wait~，其实这个和我们的扩展kmp问题没什么不一样啊~ 完全可以按照上面描述的算法求解. 综上. 我们给出扩展KMP算法的如下 c++实现.

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "stdafx.h"
#include <iostream>
#include <cstring>
#define LOCAL
using namespace std;

const int MAX_T = 255,MAX_P = 20; // 文本串最长255个字符，模式串最长20个字符

char T[MAX_T], p[MAX_P]; // 0索引不用于存储数据

int n,m, extend[MAX_T], pnext[MAX_P]; // n是T的长度, m是p的长度, extend数组见文章定义

void makenext() // 制作next数组,next[i]=LCP(p[i,..,m],p[1,...,m])
{
	int k = 1; // 注意, next[1]我们不需要使用
	while(p[k]==p[k+1]) k++;
	pnext[2] = k-1; // pnext可能是0哦~, 例如p[2]!=p[1], 则pnext[2]=0
	int a = 2,spread = a+pnext[a]-1; // spread = max{i+next[i]-1 | 1<=i<=k}, a是spread实现的下标索引
	for (k=2; k<m; k++) // 开始dp计算剩余的pnext[k+1]
	{
		if (k+pnext[k-a+2]<spread) pnext[k+1] = pnext[k-a+2];
		else
		{
			int x = spread+1, y = spread+1-k; // 开始新的比较
			if (x<k+1) x = k+1; // 因为extend可能为0,所以x完全可能<k+1
			if (!y) y = 1; // 理由同上
			while (p[x]&&p[y]&&p[x]==p[y]) x++,y++;
			pnext[k+1] = x-1-k;
			if (x-1>spread) spread = x-1, a=k+1; // 更新a和spread
		}
	}
}

void exkmp() // 扩展kmp算法, 和上面的makenext算法唯一的区别在于maxkenex算法dp的起点是pnext[2],而exkmp算法dp的起点是extend[1]
{
	int k=1,j=1;
	while(T[k]&&p[j]&&T[k] == p[j])k++,j++;
	extend[1] = k-1;
	int a = 1, spread = k-1;
	for(k = 1; k<n; k++) // dp计算extend数组
	{
		if (pnext[k-a+2]+k<spread) extend[k+1]=pnext[k-a+2];
		else
		{
			int x = spread+1,y=spread+1-k;
			if (x<k+1) x = k+1;
			if (!y) y = 1;
			while(T[x]&&p[y]&&T[x]&&T[x] == p[y])x++,y++;
			extend[k+1]=x-1-k;
			if (x-1>spread) spread = x-1, a=k+1;
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%s%s", T+1, p+1);
	n = strlen(T+1);
	m = strlen(p+1);
	makenext();
	exkmp();

	for (int i = 1; i<=n; i++)printf("%d ", extend[i]);
	return 0;
}
/*
测试数据
myGoogleyouGoogle Google
*/

最后我们讨论一下扩展KMP算法的复杂度. 注意，整个过程我们都是不断的在往前探索——没有后退, 所以复杂度是线性的 O(N+M)——一款性能不错的算法!!!

参考

【1】https://yfsyfs.github.io/2019/06/17/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E4%B9%8Bkmp/