CF::Gym 100213F – Counterfeit Money

0
11

CF::Gym题目页面传送门

有\(1\)个\(n1\times m1\)的字符矩阵\(a\)和\(1\)个\(n2\times m2\)的字符矩阵\(b\),求\(a,b\)的最大公共子矩阵。输出这个最大公共子矩阵的行数、列数和左上角分别在\(a,b\)中的坐标。若无解,输出\(\texttt{0 0}\)。若有多解,输出任意一组。

\(n1,m1,n2,m2\in[1,40]\)。

如果你还不知道Gym是什么,please点击这个

(以下假设\(n1,m1,n2,m2\)同阶,在复杂度里用\(n\)表示)

这是一个二维的字符串匹配问题。而我们只熟悉一维的字符串匹配算法,所以不妨先将\(2\)个字符矩阵一行行横着一维处理,然后再将横着一维处理所得的结果竖着一维合并。

先是横着一维处理。考虑求出\(lcP\)四维数组,其中\(lcP_{i,j,k,o}\)表示从\(a\)中的\((i,j)\)、\(b\)中的\((k,o)\)开始最多能向右延申多少个字符使得覆盖的字符串相等,即\(lcP_{i,j,k,o}=\max\limits_{a_{i,j\sim j+p-1}=b_{k,o\sim o+p-1}}\{p\}\)。这个用Z算法就可以轻松解决。显然\(lcP_{i,j,k,o}=z_{a_{i,j\sim m1}+\texttt{!}+b_{k},m1-j+2+o}\)。这样只需要对\(\forall i\in[1,n1],\forall j\in[1,m1],\forall k\in[1,n2],a_{i,j\sim m1}+\texttt{!}+b_{k}\)这\(\mathrm O\!\left(n^3\right)\)个长度为\(\mathrm O(n)\)的字符串跑Z算法即可,时间复杂度\(\mathrm O\!\left(n^4\right)\)。

然后考虑如何竖着一维合并。考虑枚举子矩阵在\(a\)中的坐标\((x1,y1)\)、在\(b\)中的坐标\((x2,y2)\),再枚举子矩阵的行数\(n’\),给它乘上能使得子矩阵在\(a,b\)中相等的最大列数\(m’\)并更新答案。显然,要满足子矩阵在\(a,b\)中匹配,就要满足在每行都匹配,即\(\forall i\in\left[1,n’\right],m’\leq lcP_{x1+i-1,y1,x2+i-1,y2}\)。那么\(m’_{\max}=\min\limits_{i=1}^{n’}\left\{lcP_{x1+i-1,y1,x2+i-1,y2}\right\}\)。这样在\(x1,y1,x2,y2\)固定时可以递推求出\(m’_{\max}\),时间复杂度\(\mathrm O\!\left(n^5\right)\)。

\(\mathrm O\!\left(n^5\right)\)有可能能过得去,但我是追求完美的OIer,当然不满足于这样卡着时限的复杂度。考虑将一些情况一并处理。不难发现在\(x1,y1,x2,y2\)固定时,\(a\)中的每个字符都唯一对应\(b\)中的\(1\)个字符(有可能越界),而对于\(2\)对左上角\(((x1_1,y1_1),(x2_1,y2_1)),((x1_2,y1_2),(x2_2,y2_2))\),若\(y1_1=y1_2,y2_1=y2_2,x1_1-x2_1=x1_2-x2_2\),则它们的字符对应情况是相等的,我们就可以把它们一起处理。这样,将可以一起处理的左上角对分到一组,就会有\(\mathrm O\!\left(n^3\right)\)组,对每一组分别处理。

由于每一组中左上角所在列固定,即对于每一行,从第几个字符开始匹配是固定的,那么对于每一组的处理可以看作这样一个问题:给定一个数列\(s\),求\(\max\limits_{i=1}^{|s|}\left\{\max\limits_{j=i}^{|s|}\left\{(j-i+1)\min\limits_{k=i}^j\{s_k\}\right\}\right\}\),其中\(s_i=lcP_{i,y1,i+x2-x1,y2}\)。考虑到\(\min\limits_{k=i}^j\{s_k\}\)一定等于\(s_{i\sim j}\)中的某一个元素,不妨枚举这个元素\(s_i\),求出它最多能往左/右延申到哪里,使得它保持最小值的身份,即设往左、右分别最多能能延申到\(up_i,dwn_i\),那么\(\forall j\in[up_i,dwn_i],s_j\geq s_i\),此时用\((dwn_i-up_i+1)s_i\)更新答案。

现在讨论怎么求\(up,dwn\)。以\(up\)为例,假设\(j<k\)且\(s_j\geq s_k\),如果\(s_k<s_i\),那么阻止\(i\)往左延申的那个元素肯定在\(k\)处或右边,不可能是\(j\);否则\(s_k\geq s_i\),结合\(s_j\geq s_k\)可以得到\(s_j\geq s_i\),\(j\)也不可能阻止\(i\)往左延申。根据这个性质,我们可以维护一个从底到顶严格单调递增的单调栈,阻止\(i\)往左延申的元素只可能在栈内。维护单调栈显然是\(\mathrm O(|s|)\)的。\(\forall i\in[1,|s|]\),可以在单调栈内二分找到阻止\(i\)往左延申的元素,这样一组中求\(up\)的时间复杂度为\(\mathrm O(|s|\log |s|)\)。然而其实根本不用二分,因为我们要找的是栈中最上面的\(j\)使得\(s_j<s_i\),而在将\(i\)入栈之前维护栈顶单调性时将所有栈顶的满足\(s_j\ge s_i\)的\(j\)弹出了,剩下来的栈顶就是我们要找的了(如果栈为空,则没有可以阻止\(i\)往左延申的元素,可以一直延伸到最左边)。这样每组求\(up\)复杂度\(\mathrm O(|s|)\)。\(dwn\)类似,所以每组总复杂度\(\mathrm O(|s|)=\mathrm O(n)\)。

一共\(\mathrm O\!\left(n^3\right)\)组,每组\(\mathrm O(n)\),总复杂度\(\mathrm O\!\left(n^4\right)\)。我们要写复杂度正确的算法,不能像窝女朋友libra9z一样写个\(\mathrm O\!\left(n^6\right)\)算法加剪枝水过去。。。

下面贴代码:(记得文件输入输出)

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int N=40;
int n1,m1,n2,m2;//2个字符矩阵大小 
char a[N+1][N+5],b[N+1][N+5];//2个字符矩阵 
int s;//c的长度 
char c[2*N+6];//临时字符串 
void con(int x,int y,int z){//令c=a[x][y~m1]+'!'+b[z] 
	s=0;
	for(int i=y;i<=m1;i++)c[++s]=a[x][i];
	c[++s]='!';
	for(int i=1;i<=m2;i++)c[++s]=b[z][i];
}
int z[2*N+6];//c的z数组 
void z_init(){//对c跑Z算法 
	int zl=0,zr=0;
	z[1]=s;
	for(int i=2;i<=s;i++)
		if(zr<i){
			z[i]=0;
			while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
			if(z[i])zl=i,zr=i+z[i]-1;
		}
		else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
		else{
			z[i]=zr-i+1;
			while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
			zl=i;zr=i+z[i]-1;
		}
}
int lcP[N+1][N+1][N+1][N+1];//lcP[i][j][k][o]表示从a中的(i,j)、b中的(k,o)开始最多能向右延申多少个字符使得覆盖的字符串相等
int up[N],dwn[N];//从i开始最多能往左、右延伸到up[i],dwn[i] 
int stk[N],top;//单调栈 
int main(){
	freopen("money.in","r",stdin);freopen("money.out","w",stdout);
	cin>>n1>>m1;
	for(int i=1;i<=n1;i++)cin>>a[i]+1;
	cin>>n2>>m2;
	for(int i=1;i<=n2;i++)cin>>b[i]+1;
	for(int i=1;i<=n1;i++)for(int j=1;j<=m1;j++)for(int k=1;k<=n2;k++){//求lcP数组 
		con(i,j,k);
		z_init();
		for(int o=1;o<=m2;o++)lcP[i][j][k][o]=z[m1-j+1+1+o];
	}
//	for(int i=1;i<=n1;i++)for(int j=1;j<=m1;j++)for(int k=1;k<=n2;k++)for(int o=1;o<=m2;o++)
//		printf("lcP[(%d,%d)][(%d,%d)]=%d\n",i,j,k,o,lcP[i][j][k][o]);
	pair<int,pair<pair<int,int>,pair<pair<int,int>,pair<int,int> > > > ans;//答案(以大小为关键字比较) 
	ans.X=0; 
	for(int i=1;i<=m1;i++)/*y1*/for(int j=1;j<=m2;j++)/*y2*/for(int k=-min(n1,n2)+1;k<min(n1,n2);k++)/*x2-x1*/{//枚举每组 
//		printf("i=%d j=%d k=%d:\n",i,j,k);
		vector<pair<int,int> > v;//数列s,越界不计入 
		for(int o=1;o<=n1;o++)if(1<=o+k&&o+k<=n2)/*判越界*/v.pb(mp(o,lcP[o][i][o+k][j]));
		//求up 
		top=0;//清空单调栈 
		for(int o=0;o<v.size();o++){
			while(top&&v[stk[top-1]].Y>=v[o].Y)top--;//维护栈顶单调性 
			up[o]=top?stk[top-1]+1:0;//栈顶为阻止o向左延伸的元素 
			stk[top++]=o;//将o入队 
		}
		//求dwn 
		top=0;//清空单调栈
		for(int o=v.size()-1;~o;o--){
			while(top&&v[stk[top-1]].Y>=v[o].Y)top--;//维护栈顶单调性 
			dwn[o]=top?stk[top-1]-1:v.size()-1;//栈顶为阻止o向右延伸的元素 
			stk[top++]=o;//将o入队
		}
//		for(int o=0;o<v.size();o++)printf("\tup[%d]=%d dwn[%d]=%d\n",o,up[o],o,dwn[o]);
		for(int o=0;o<v.size();o++){//枚举最小值 
			int u=up[o],d=dwn[o];//左右边界 
			ans=max(ans,mp((d-u+1)*v[o].Y,mp(mp(d-u+1,v[o].Y),mp(mp(v[u].X,i),mp(v[u].X+k,j)))));//更新答案 
		}
	}
//	cout<<ans.X<<"\n";
	if(ans.X==0)puts("0 0");
	else printf("%d %d\n%d %d\n%d %d",ans.Y.X.X,ans.Y.X.Y,ans.Y.Y.X.X,ans.Y.Y.X.Y,ans.Y.Y.Y.X,ans.Y.Y.Y.Y);
	return 0;
}

<

发布回复

请输入评论!
请输入你的名字