"CodeForces Gym題目頁面傳送門" 有$1$個$n1\times m1$的字元矩陣$a$和$1$個$n2\times m2$的字元矩陣$b$，求$a,b$的最大公共子矩陣。輸出這個最大公共子矩陣的行數、列數和左上角分別在$a,b$中的坐標。若無解，輸出$``\text{0 0''}$。若 ...
CodeForces 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}\)，時間複雜度\(\operatorname 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_2|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;
}
