题意 在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; }