题目描述
每天早上,农夫约翰的奶牛们被挤奶的时候,都会站成一个R行C列的方阵。
现在在每个奶牛的身上标注表示其品种的大写字母,则所有奶牛共同构成了一个R行C列的字符矩阵。
现在给定由所有奶牛构成的矩阵,求它的最小覆盖子矩阵的面积是多少。
如果一个子矩阵无限复制扩张之后得到的矩阵能包含原来的矩阵,则称该子矩阵为覆盖子矩阵。
样例
输入样例:
2 5
ABABA
ABABA
输出样例:
2
提示
样例中给出的矩阵的最小覆盖子矩阵为AB,面积为2。
算法1
(kmp)
1.先枚举循环节长度,再判断当前行循环节是否为j
2.再用kmp对行进行计算。
注意: 用最短的循环节可以保证纵向求的循环节不会变长。(假设有长度为a, b的循环节,a < b, 用长度为b的循环节去对每一行进行kmp操作,会导致可能next[b]
比next[a]
的大,因为next[b]
包含next[a]
)
所以用短的循环节,求出的面积一定会比长的循环节面积要小。
时间复杂度
代码中需要注意的点
st
与视频中代码相反,不影响结果。
第一部分循环代表的意思,见下图
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = 80;
int n, m;
char str[N][M];
bool st[M];
int ne[N];
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i ++){//枚举行
cin >> str[i];
for (int j = 1; j <= m; j ++){//枚举当前列的循环节长度
bool is_match = true;
for (int k = j; k < m; k += j){//枚举起点
for (int u = 0; u < j && k + u < m; u ++)//u从0到j
if (str[i][u] != str[i][k + u]){
is_match = false;
break;
}
if (!is_match) break;
}
if (!is_match) st[j] = true;
}
}
int width;
for (int i = 1; i <= m; i ++)
if (!st[i]){
width = i;
break;
}
for (int i = 1; i <= n; i ++) str[i][width] = 0;
for (int i = 2, j = 0; i <= n; i ++){
while (j && strcmp(str[j + 1], str[i])) j = ne[j];
if (!strcmp(str[j + 1], str[i])) j ++;
ne[i] = j;
}
int height = n - ne[n];
cout << width * height << endl;
return 0;
}