Milking Grid poj2185

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 #define maxn 1000008
 8 
 9 char s[maxn][80];
10 int r, c, next[maxn];
11 
12 bool same1(int i, int j)   // 判断第i行和第j行是否相等
13 {
14     for(int k = 0; k < c; k++)
15         if(s[i][k] != s[j][k])
16             return false;
17     return true;
18 }
19 
20 bool same2(int i, int j)  // 判断第i列和第j列是否相等。
21 {
22     for(int k = 0; k < r; k++)
23         if(s[k][i] != s[k][j])
24             return false;
25     return true;
26 }
27 
28 int main()
29 {
30     while(~scanf("%d%d", &r, &c))
31     {
32         for(int i = 0; i < r; i++)
33             scanf("%s", s[i]);
34         int j, k;
35         memset(next, 0, sizeof(next));
36         j = 0;
37         k = next[0] = -1;
38         while(j < r)
39         {
40             while(-1 != k && !same1(j, k))
41                 k = next[k];
42             next[++j] = ++k;
43         }
44         int ans1 = r - next[r];     //  r-next[r]就是需要的最短的长度可以覆盖这个平面
45         memset(next, 0, sizeof(next));
46         j = 0;
47         k = next[0] = -1;
48         while(j < c)
49         {
50             while(-1 != k && !same2(j, k))
51                 k = next[k];
52             next[++j] = ++k;
53         }
54         int ans2 = c - next[c];  //列的 
55 
56         printf("%d\n", ans1*ans2);
57     }
58     return 0;
59 }