poj2185 kmp求最小覆盖矩阵，好题！

/* 特征值k=m-next[m]就是最小循环节的长度， m%k就是去末尾遗留长度 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; char strs[10005][100]; int r,c,w,h,f[1050],nxt[10005];//r是行，c是列 void kmp_pre1(char *s){//求一行的nxt数组 int nxtt[1005]={}; int m=strlen(s); int i,j; i=0;j=nxtt[0]=-1; while(i<m){ while(j!=-1 && s[i]!=s[j]) j=nxtt[j]; nxtt[++i]=++j; } //把可行的长度都在f中+1 int tmp=m-nxtt[m],k=0; while(k+tmp<=m){ k+=tmp; f[k]++; } //剩下的串枚举一次开头就好 for(k=m%(m-nxtt[m]);k;k=nxtt[k]){ f[m-nxtt[k]]++; } } void kmp_pre2(){ memset(nxt,0,sizeof nxt); int i,j; i=0,j=nxt[0]=-1; while(i<r){ while(j!=-1 && strcmp(strs[i],strs[j])!=0) j=nxt[j]; nxt[++i]=++j; } } int main(){ while(scanf("%d%d",&r,&c)==2){ memset(f,0,sizeof f);//宽度为i的子串出现的次数 w=c,h=r; for(int i=0;i<r;i++){ scanf("%s",strs[i]); kmp_pre1(strs[i]); } for(int i=1;i<=c;i++)//找到矩阵最小宽度 if(f[i]==r){w=i;break;} for(int i=0;i<r;i++) strs[i][w]='\0';//截取前w个字符 kmp_pre2();//获取在行之间的next数组 h=r-nxt[r];//h就是列上的特征值 printf("%d\n",w*h); } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/10273749.html