本文主要是介绍POJ 2185 Milking Grid(KMP 经典)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=2185
这个题目其实难度不大，但是要想很顺利的做出来对kmp没有一定程度的理解还是不行的
这个题目要求的是一个最小的矩形然后看看这个矩形的字符串扩展能不能形成整个大的矩形
串，形成的大的矩形包含原来矩形也算
首先这个矩形一定是在左上角这个是没什么疑问的，下面就是求循环节了，这个怎么求呢
这里给出的方法是整体求kmp的next，利用kmp的next值来求循环节，直接n-next[n]所以
这里求的循环节的长度如果能被整个串长度正除，那么就是整个串的循环节，否则（其实
也是）这个求来的循环节的扩展包括整个串
这个题目在求next的时候求横着的next的时候将每一列看成一个整体，求列的next的时候
将行看成一个整体，这样求两次next求出循环节相乘就OK 了！
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 10010
char str[maxn][100];
int next[maxn],n,m;
bool equal_row(int i,int j){for(int k=0;k<n;k++)if(str[k][i]!=str[k][j])return false;return true;
}
bool equal_colunm(int i,int j){for(int k=0;k<m;k++)if(str[i][k]!=str[j][k])return false;return true;
}
int get_next_row(char *s){int i=0,j=-1;next[0]=-1;while(s[i]){if(j==-1 || equal_row(i,j))i++,j++,next[i]=j;elsej=next[j];}return m-next[m];
}
int get_next_colunm(int p){int i=0,j=-1;next[0]=-1;while(str[i][p]){if(j==-1 || equal_colunm(i,j))i++,j++,next[i]=j;elsej=next[j];}return n-next[n];
}
int main(){int i,j,k,ans1,ans2;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<n;i++)scanf("%s",str[i]);for(i=0;i<100;i++)str[n][i]=0;ans1=get_next_row(str[0]);ans2=get_next_colunm(0);printf("%d\n",ans1*ans2);}return 0;
}
这篇关于POJ 2185 Milking Grid(KMP 经典)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
