首页 > 代码库 > 【kmp算法】poj2185 Milking Grid
【kmp算法】poj2185 Milking Grid
先对每行求出所有可能的循环节长度(不需要整除)。
然后取在所有行中都出现了的,且最小的长度为宽。
然后将每一行看作字符,对所有行求next数组,将n-next[n](对这些行来说最小的循环节长度)作为长。
最后输出长乘宽即可。
#include<cstdio> #include<cstring> using namespace std; bool can[10010][80]; char s[10010][80]; int next[80],n,m,wide,NEXT[10010]; void GetFail(char P[],int next[])//next[i]表示s[0]~s[i-1]的前缀中,最大相等的前后缀的长度是多少 { next[0]=-1; int len=strlen(P); for(int i=0;i<len;i++) { int j=next[i]; while(j>=0 && P[i]!=P[j]) j=next[j]; if(j!=-1 && P[i]==P[j]) next[i+1]=j+1; else next[i+1]=0; } } int main() { // freopen("poj2185.in","r",stdin); scanf("%d%d",&n,&m); for(int i=0;i<n;++i) { scanf("%s",s[i]); GetFail(s[i],next); for(int j=next[m];j!=-1;j=next[j]) can[i][m-j]=1; } for(int j=1;j<=m;++j) { bool flag=1; for(int i=0;i<n;++i) if(!can[i][j]) { flag=0; break; } if(flag) { wide=j; break; } } for(int i=0;i<n;++i) s[i][wide]=‘\0‘; next[0]=-1; int len=n; for(int i=0;i<len;i++) { int j=next[i]; while(j>=0 && strcmp(s[i],s[j])!=0) j=next[j]; if(j!=-1 && strcmp(s[i],s[j])==0) next[i+1]=j+1; else next[i+1]=0; } printf("%d\n",wide*(n-next[n])); return 0; }
【kmp算法】poj2185 Milking Grid
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。