exkmp略解

推导

ext[i]表示母串s[i..lens]和子串t[1..lent]的最长公共前缀。

nxt[i]表示t[i..lent]和t[1..lent]的最长公共前缀。

假设ext[1..k]已经算好，现在想求ext[k]。

我们先找出1..k中，i+ext[i]-1的最大值p，并且记此时的i为a。

可知s[a..p]=t[1..p-a+1]，自然有s[k+1..p]=t[k-a+2..p-a+1]，记l=nxt[k-a+2]。

出现两种情况：

k+l<p

可想而知，ext[k+1]=l
k+l>=p

这样会发现有未知情况，因此就再度匹配，直至适配，然后更新a。

int lena, lenb, nxt[100005], ext[100005];

char a[100005], b[100005];

void mknxt(){

	int j=0, po;

	nxt[0] = lenb;

	while(j+1<lenb && b[j]==b[j+1])	j++;

	nxt[1] = j;

	po = 1;

	for(int i=2; i<len; i++){

		if(i+nxt[i-po]<nxt[po]+po)

			nxt[i] = nxt[i-po];

		else{

			j = max(nxt[po] + po - i, 0);

			while(i+j<lenb && b[i+j]==b[j])	j++;

			nxt[i] = j;

			po = i;

		}

	}

}

void exkmp(){

	int j=0, po;

	while(a[j]==b[j] && j<lena && j<lenb)

		j++;

	ext[0] = j;

	po = 0;

	for(int i=1; i<lena; i++){

		if(nxt[i-po]+i<ext[po]+po)

			ex[i] = nxt[i-po];

		else{

			j = max(ex[po] + po - i, 0);

			while(i+j<lena && j<lenb && a[i+j]==b[j])	j++;

			ext[i] = j;

			po = i;

		}

	}

}

巴特西

exkmp略解

推导

最新文章

热门文章