扩展KMP模板

• 2018-02-21
• 0
• 0

本文主要介绍扩展 KMP 算法，普通 KMP 算法请见[POJ 3461] Oulipo【KMP】。

对于两个串 S[0, n) 和 T[0, m)，我们需要 O(n+m) 求出 S[i, n) 和 T 的最长公共前缀序列 lcp[i]。

设 nxt[i] 表示 T[i, m) 和 T 最长公共前缀，当前正在匹配的左端点为 a，第一个失配的位置为 p。

易得 S[a, p) == T[0, p - a)，分类讨论：

1. 若 i + nxt[i - a] < p，则如下图，lcp[i] = nxt[i - a]。
2. 若 i + nxt[i - a] == p，则如下图，从 S[p] 和 T[p - i] 开始暴力匹配即可。
3. 若 i + nxt[i - a] > p，则如下图，lcp[i] = p - i。

我们发现，nxt[] 本质上是一次自匹配公共前缀的过程，模仿 lcp[] 的求解方法即可求得。

Code: 单组数据 O(|S|+|T|)

// 扩展 KMP 算法 (2018.2.21)
/*
  S	|_______|____________________|______|_________|
	0       a                    i      p       Slen-1
	
	      T |______|_____________|______|_______|
	        0     p-i           i-a    p-a    Tlen-1
	            nxt[i-a]?
	
	设 S[a, p) 与 T[0, p - a) 匹配, 
	则当 S[p] != T[p - a] 时, 若 
		1) i + nxt[i - a] < p, 则 lcp[i] = nxt[i - a] 
		2) i + nxt[i - a] == p, 则从 S[p] 和 T[p - i] 开始往后暴力比较 
		3) i + nxt[i - a] > p, 则 lcp[i] = p - i 
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

char S[1000005], T[1000005];
int Slen, Tlen, nxt[1000005], lcp[1000005];

int main(){
	while(scanf("%s%s", S, T) != EOF){
		Slen = strlen(S), Tlen = strlen(T);
		nxt[0] = Tlen;
		for(register int i = 1, a = 0, p = 0; i < Tlen; i++){
			if(i + nxt[i - a] >= p){
				if(i > p) p = i;
				while(p < Tlen && T[p] == T[p - i]) p++;
				nxt[i] = p - i, a = i;
			}
			else nxt[i] = nxt[i - a];
		}
		for(register int i = 0, a = 0, p = 0; i < Slen; i++){
			if(i + nxt[i - a] >= p){
				if(i > p) p = i;
				while(p < Slen && S[p] == T[p - i]) p++;
				lcp[i] = p - i, a = i;
			}
			else lcp[i] = nxt[i - a];
		}
		for(register int i = 0; i < Slen - 1; i++) printf("%d ", lcp[i]);
		printf("%d\n", lcp[Slen - 1]);
	}
	return 0;
}