題意 在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;}新聞熱點
疑難解答
