POJ 2185

题目链接：

题目描述：

　　给定一个R * C的矩阵，在该矩阵中寻找一个子矩阵，要求子矩阵复制多次能够包含原矩阵。

解题思路：

　　如果在字符串中找到一个最小子串使其复制多次包含原字符串，那么我们可以很容易想到通过kmp算法的next数组来得出该子串长度，即len - next[len]。

　　那么回到这道题，要在矩阵中找到合法的最小子矩阵，其实跟找最小子串的原理是一样的，只需要对矩阵的行和列分别看成一个字符串用kmp算法过一遍，然后分别得到一个最小行数，该行数复制多遍可以包含原矩阵，以及一个最小列数，该列数复制多遍同样可以包含原矩阵，那么题目要求的子矩阵宽和高就这样得到了，最后相乘一下输出就搞定啦。

代码：

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <map>
 6 #include <vector>
 7 #include <algorithm>
 8 using namespace std;
 9 
10 #define ll long long
11 #define INF 0x3f3f3f3f3f
12 #define MAX 
13 
14 char rectangle[10010][100];
15 int fail[10010];
16 int R, C;
17 
18 /*
19 判断矩阵行与行之间是否相等
20  */
21 bool cmp1(int j, int k)
22 {
23     for(int i = 0; i < C; ++i) {
24         if(rectangle[j][i] != rectangle[k][i])
25             return 0;
26     }
27     return 1;
28 }
29 
30 /*
31 判断矩阵列与列之间是否相等
32  */
33 bool cmp2(int j, int k)
34 {
35     for(int i = 0; i < R; ++i) {
36         if(rectangle[i][j] != rectangle[i][k])
37             return 0;
38     }
39     return 1;
40 }
41 
42 int main()
43 {
44     //freopen("debug\in.txt", "r", stdin);
45     //freopen("CON", "w", stdout);
46     int i, j, k;
47     scanf("%d%d", &R, &C);
48     for(i = 0; i < R; ++i) {
49         scanf("%s", rectangle[i]);
50     }
51     fail[0] = k = -1;
52     j = 0;
53     //kmp获取next数组的超简洁版写法
54     while(j < R) {
55         while(k != -1 && !cmp1(j, k)) k = fail[k];
56         fail[++j] = ++k;
57     }
58     int ans1 = R - fail[R]; //获得子矩阵高
59     fail[0] = k = -1;
60     j = 0;
61     while(j < C) {
62         while(k != -1 && !cmp2(j, k)) k = fail[k];
63         fail[++j] = ++k;
64     }
65     int ans2 = C - fail[C]; //获得子矩阵宽
66     printf("%d
", ans1 * ans2);
67     return 0；
68 }