题目大意

给定一个 n×m 的矩阵，每个位置有一个大写字母。请求出这个矩阵本质不同的子矩阵的个数（参考字符串本质不同的子串）。 1≤n,m≤110

---

题目分析

一个很 naive 的想法，暴力枚举，然后使用多哈希 O(1) 判断，时间复杂度 O(n4) 。 然而这题我们可以使用一种更高的姿势水平玩哈希。枚举子矩阵宽度 w ，我们要统计宽度为w的矩阵对答案的贡献，显然一个宽度为 w 的矩阵可以有多个宽度为w高度为 1 的矩阵上下拼接而成。我们将所有宽度为w高度为 1 的子矩阵用哈希压成数值，就可以去掉考虑一维。当然不同列开头的不能上下连接，于是我们在列与列之间要加上特殊数值。 问题变为求这个数组的本质不同的连续子序列个数，这是后缀数组和后缀自动机的经典问题。当然这题后缀自动机要使用map来存边，时间复杂度和后缀数组一样都是 O(n3log2n2) 的。 可能有点难理解，可以参考一下我的代码。

---

代码实现

#include <algorithm> #include <iostream> #include <cstdio> #include <cctype> using namespace std; typedef pair<int,int> P; #define mkp(a,b) make_pair(a,b) #define ft first #define sd second const int MOD=1004535809; const int P0=3873383; const int P1=9598609; const int N=120; const int M=120; const int S=N*M; int Ws[S],Wv[S],x[S],y[S],SA[S],rank[S],height[S]; int n,m,cnt,len; int pw[2][M],rp[2][M]; int hash[2][N][M]; char s[N][M]; P a[S]; int quick_power(int x,int y) { int ret=1; for (;y;y>>=1,x=1ll*x*x%MOD) if (y&1) ret=1ll*ret*x%MOD; return ret; } void pre() { pw[0][0]=1; for (int i=1;i<=m;i++) pw[0][i]=1ll*pw[0][i-1]*P0%MOD; rp[0][m]=quick_power(pw[0][m],MOD-2); for (int i=m-1;i>=0;i--) rp[0][i]=1ll*rp[0][i+1]*P0%MOD; for (int i=0;i<n;i++) { hash[0][i][0]=s[i][0]; for (int j=1;j<m;j++) hash[0][i][j]=(hash[0][i][j-1]+1ll*pw[0][j]*s[i][j])%MOD; } pw[1][0]=1; for (int i=1;i<=m;i++) pw[1][i]=1ll*pw[1][i-1]*P1%MOD; rp[1][m]=quick_power(pw[1][m],MOD-2); for (int i=m-1;i>=0;i--) rp[1][i]=1ll*rp[1][i+1]*P1%MOD; for (int i=0;i<n;i++) { hash[1][i][0]=s[i][0]; for (int j=1;j<m;j++) hash[1][i][j]=(hash[1][i][j-1]+1ll*pw[1][j]*s[i][j])%MOD; } } void build(int w) { len=0; for (int j=0;j<m-w+1;j++) { for (int i=0;i<n;i++) a[len++]=mkp(1ll*(hash[0][i][j+w-1]-(j?hash[0][i][j-1]:0)+MOD)%MOD*rp[0][j]%MOD,1ll*(hash[1][i][j+w-1]-(j?hash[1][i][j-1]:0)+MOD)%MOD*rp[1][j]%MOD); a[len++]=mkp(-(j+1),-(j+1)); } } bool cmp(int *r,int st1,int st2,int l){return st1+l>=len||st2+l>=len||r[st1]!=r[st2]||r[st1+l]!=r[st2+l];} bool compare(int x,int y){return a[x]<a[y];} void DA() { int i,p,l,mx; for (i=0;i<len;i++) SA[i]=i; sort(SA,SA+len,compare); for (x[SA[0]]=p=0,i=1;i<len;i++) x[SA[i]]=(p+=a[SA[i]]!=a[SA[i-1]]); for (l=1;l<=len&&p!=len-1;l<<=1) { for (p=0,i=len-l;i<len;i++) y[p++]=i; for (i=0;i<len;i++) if (SA[i]>=l) y[p++]=SA[i]-l; for (i=0,mx=0;i<len;i++) mx=max(mx,Wv[i]=x[y[i]]); for (i=0;i<=mx;i++) Ws[i]=0; for (i=0;i<len;i++) Ws[Wv[i]]++; for (i=1;i<=mx;i++) Ws[i]+=Ws[i-1]; for (i=len-1;i>=0;i--) SA[--Ws[Wv[i]]]=y[i]; for (i=0;i<len;i++) y[i]=x[i],x[i]=0; for (x[SA[0]]=p=0,i=1;i<len;i++) x[SA[i]]=(p+=cmp(y,SA[i],SA[i-1],l)); } for (i=0;i<len;i++) rank[SA[i]]=i; } void getheight() { for (int k=0,i=0,j;i<len;i++) { k?--k:k; if (!rank[i]) continue; for (j=SA[rank[i]-1];j+k<len&&i+k<len&&a[j+k]==a[i+k];) k++; height[rank[i]]=k; } } void count() { for (int i=0;i<len;i++) if (a[SA[i]].ft>=0) cnt+=((SA[i]+1)/(n+1)*(n+1)+n-SA[i]-height[i]); } int main() { freopen("matrix.in","r",stdin),freopen("matrix.out","w",stdout); scanf("%d%d",&n,&m); for (int i=0;i<n;i++) scanf("%s",s[i]); pre(); for (int w=1;w<=m;w++) build(w),DA(),getheight(),count(); printf("%d\n",cnt); fclose(stdin),fclose(stdout); return 0; }