扩展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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai