题意 在N*M字符矩阵中找出一个最小子矩阵，使其多次复制所得的矩阵包含原矩阵。N<=10000,M<=75 aba bab aba
ab ba
解法 先找出最大的K，使得原矩阵是若干个K*M的矩阵拼成一列后的子矩阵 把一行看做一个整体，对列做KMP 用应用1的方法确定最小行宽 再在K*M的矩阵中，把一列看做一个整体，用同样的方法求最小行宽 O(N*M)
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int N=10005;char w[N][80];int t[N],l[80],n,m,tmp;void calc_t(){ t[0]=-1; int j; for (int i=0;i<n;i++) { t[i+1]=i+1; for (int k=0;k<m;k++) { j=t[i]; while(w[i][k]!=w[j][k]&&j!=-1) j=t[j]; t[i+1]=min(++j,t[i+1]); } }}void calc_w(){ int j; l[0]=-1; for (int i=0;i<m;i++) { l[i+1]=i+1; for (int k=0;k<tmp;k++) { j=l[i]; while(w[k][i]!=w[k][j]&&j!=-1) j=l[j]; l[i+1]=min(++j,l[i+1]); } }}int main(){// freopen("std.in","r",stdin); cin>>n>>m; for (int i=0;i<n;i++) scanf("%s",w[i]); calc_t(); tmp=n-t[n]; calc_w(); int tmp1=m-l[m]; cout<<tmp*tmp1; return 0;}新闻热点
疑难解答
