题目

题目大意

给你两个字符串\(A\)和\(B\)，可以修改\(A\)中的一个字符，求修改后最长的\(A\)的前缀，使它是\(B\)的子串。

思考历程

看到这道题之后，第一眼想到的就是后缀自动机！

\(B\)的子串，意味着可以把\(B\)建立一个后缀自动机，然后在上面跑……

刚开始的想法是将\(A\)在上面跑，并且试着修改后面一个字符，看看剩下的可以跑多长……

于是问题就转化成求这样的一个东西：问\(A\)的某个后缀从后缀自动机上的某个节点开始最多能跑多远。

我试着将这个东西预处理出来……可是没有成功……

交了个错误的程序上去，居然还有点分。

水法

这题不得不开“水法”这一栏目。

题目的数据真是太水了，各种暴力都能过。

最简单的暴力：枚举子串的左端点，然后暴力匹配，遇见的第一个不同就用掉修改机会，求出匹配的最大长度。

还有一种\(O(n)\)的正确性显然错误的DP……

跑得都比正解快……

正解

有个exkmp的方法，虽然说时间可能会有点玄学，但既然是郑姐讲的方法，就把它归为“正解”这一栏吧……

求出\(A\)的\(next\)，以\(A\)为模式串求出\(B\)的\(extend\)。

枚举子串的开头\(i\)，则后面相同的子串长度为\(extend_i\)。

后面那个位置用修改操作，所以要从\(A_{extend_i+2}\)和\(B_{i+extend_i+1}\)开始继续匹配。

接下来取\(\min(next_{extend_i+2},extend_{i+extend_i+1})\)。后面这个长度的串一定是相同的，因为前者等于\(A\)前面一段，后者也等于\(A\)前面一段，其中的最小值就是它们相等的长度。

然而这可能不是极限，所以后面的，就暴力判断吧……

时间应该比较优秀，虽然说那一部分暴力判断有点玄学……

然后是题解中的\(LCP\)做法。

先枚举子串的左端点\(i\)，求\(LCP(B_{i..m},A)\)，设为\(x\)。\(x+1\)位可以用修改机会，然后求\(LCP(A_{x+2..n},B_{i+x+1..m})\)，就是后面能继续延伸的长度。

当然，记得判断一下到达边界的情况。

至于求\(LCP\)，最典型的做法是用后缀数组，将\(A\)和\(B\)并在一起，中间用特殊字符隔开，然后求后缀数组和\(height\)数组，然后用数据结构维护区间\(height\)最小值。

还有一种做法是用后缀自动机。考虑利用\(fail\)指针，如果跳两个节点在\(fail\)树上的\(LCA\)，它的\(len\)就是它们的最长公共后缀。要求最长公共前缀，就把字符串倒过来建后缀自动机就行了……（\(fail\)树实际上是逆序字符串的后缀树）这是两个字符串，所以要建广义后缀自动机。

最后是许多人使用的二分和\(hash\)做法。

首先二分答案\(k\)，将\(B\)串中长度为\(k\)的子串存入\(hash\)表。

然后\(26n\)来枚举修改的方案，每次修改后再\(hash\)表中查询。

代码

后缀自动机的做法……

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cassert>

#define N 50010

int n,m;

char a[N],b[N];

struct Node{

	Node *c[26],*fail;

	int len;

} d[N*4];

int cnt;

Node *S,*last;

inline void insert(int ch){

	if (last->c[ch] && last->c[ch]->len==last->len+1){

		last=last->c[ch];

		return;

	}

	Node *nw=&d[++cnt],*p;

	nw->len=last->len+1;

	for (p=last;p && !p->c[ch];p=p->fail)

		p->c[ch]=nw;

	if (!p)

		nw->fail=S;

	else{

		Node *q=p->c[ch];

		if (p->len+1==q->len)

			nw->fail=q;

		else{

			Node *clone=&d[++cnt];

			memcpy(clone,q,sizeof(Node));

			clone->len=p->len+1;

			for (;p && p->c[ch]==q;p=p->fail)

				p->c[ch]=clone;

			nw->fail=q->fail=clone;

		}

	}

	last=nw;

}

int sta[N],stb[N];

int fa[N*4][17],dep[N*4];

int get_dep(int x){

	if (dep[x])

		return dep[x];

	if (!fa[x][0])

		return dep[x]=1;

	return dep[x]=get_dep(fa[x][0])+1;

}

int LCP(int u,int v){

	if (dep[u]<dep[v])

		swap(u,v);

	for (int k=dep[u]-dep[v],i=0;k;k>>=1,++i)

		if (k&1)

			u=fa[u][i];

	if (u==v)

		return d[u].len;

	for (int i=16;i>=0;--i)

		if (fa[u][i]!=fa[v][i])

			u=fa[u][i],v=fa[v][i];

	return d[fa[u][0]].len;

}

int main(){

	scanf("%s%s",a+1,b+1);

	n=strlen(a+1),m=strlen(b+1);

	n=min(n,m);

	last=S=&d[++cnt];

	for (int i=m;i>=1;--i){

		insert(b[i]-'a');

		stb[i]=last-d;

	}

	last=S;

	for (int i=n;i>=1;--i){

		insert(a[i]-'a');

		sta[i]=last-d;

	}

	fa[1][0]=0;

	for (int i=2;i<=cnt;++i)

		fa[i][0]=d[i].fail-d;

	for (int i=1;i<=cnt;++i)

		get_dep(i);

	for (int i=1;i<=16;++i)

		for (int j=1;j<=cnt;++j)

			fa[j][i]=fa[fa[j][i-1]][i-1];

	int ans=0;

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

		int lcp=LCP(stb[i],sta[1]);

		if (lcp==n || lcp==n-1){

			printf("%d\n",n);

			return 0;

		}

		ans=max(ans,lcp+(i+lcp<=m?1:0)+(i+lcp+1<=m?LCP(stb[i+lcp+1],sta[1+lcp+1]):0));

	}

	printf("%d\n",ans);

	return 0;

}

总结

这题应该算是一道套路题吧……

所以看题的时候，不要试着死磕一个地方，要多方面地去考虑……

比如，枚举左端点右端点什么的……

巴特西

[JZOJ3337] 【NOI2013模拟】wyl8899的TLE

题目

题目大意

思考历程

水法

正解

代码

总结

最新文章

热门文章