poj2185 Milking Grid

题目链接：http://poj.org/problem?id=2185

这道题我看了好久，最后是通过参考kuangbin的博客才写出来的

感觉next数组的应用自己还是掌握的不够深入

这道题其实就是先对于每一行字符串计算next数组(就是把每一行的字符串当作单个字符啦)，最后n-next[n]即为n行字符串的最小重复单元

然后对于每一列字符串计算next数组，最后m-len[m]即为m列的最小重复单元

由于答案是求最小覆盖单元的面积

所以答案即为(n-len[n])*(m-len(m));

感觉很妙啊！！！

代码如下：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,m;
 6 int f[10010];
 7 char s[10010][100];
 8 bool Is_same_cow(int i,int j)
 9 {
10      for(int kk=0;kk<m;kk++)
11           if(s[i][kk]!=s[j][kk])  return false;
12          return true;
13 
14 }
15 bool Is_same_row(int i,int j)
16 {
17      for(int kk=0;kk<n;kk++)
18         if(s[kk][i]!=s[kk][j]) return false;
19         return true;
20 }
21 
22 int main()
23 {
24      while(scanf("%d%d",&n,&m)!=EOF)
25      {
26          for(int i=0;i<n;i++) scanf("%s",s[i]);
27         int i,j=0,k=-1;
28         f[0]=-1;
29         while(j<n)
30         {
31              if(k==-1|| Is_same_cow(j,k)) 
32              {
33                   j++;k++;
34                   f[j]=k;
35              }
36              else k=f[k];
37         }
38         int ans1=n-f[n];
39        j=0,k=-1;
40        f[0]=-1;
41        while(j<m)
42        {
43            if(k==-1|| Is_same_row(j,k)) 
44            {
45                j++;k++;
46                f[j]=k;
47            }
48            else k=f[k];
49 
50        }
51        int ans2=m-f[m];
52        cout<<ans1*ans2<<endl;
53 
54      }
55      return 0;
56 }

View Code