自动搬运

查看原文

来自洛谷，原作者为

	SkyLines Everything is nothing without you. You make it happen.

搬运于2025-08-24 22:58:19，当前版本为作者最后更新于2024-05-27 14:28:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

因为这个矩形要重复，所以可以求出行最小和列最小的值，相乘即为答案。

求每行和每列的 Hash 值，求行和列的最小循环节长度即为最小值，求法见 Link.，可用 Hash 或 KMP 做。

Code

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N = 10005, p = 131, M = 75;
int r, c, a[N], b[M], nxt[N], ans, ans2, j;
string s[N];
signed main(){
	cin >> r >> c;
	for(int i = 1; i <= r; i++){
		cin >> s[i];
		s[i] = " " + s[i];
		for(int j = 1; j <= c; j++){
			a[i] = a[i] * p + s[i][j];
		}
	}
	for(int i = 1; i <= c; i++){
		for(int j = 1; j <= r; j++){
			b[i] = b[i] * p + s[j][i];
		}
	}
	nxt[1] = 0;
	j = 0;
	for(int i = 2; i <= r; i++){
		while(j && a[i] != a[j + 1]) j = nxt[j];
		if(a[i] == a[j + 1]) j++;
		nxt[i] = j;
	}
	ans = r - nxt[r];
	nxt[1] = 0;
	j = 0;
	for(int i = 2; i <= c; i++){
		while(j && b[i] != b[j + 1]) j = nxt[j];
		if(b[i] == b[j + 1]) j++;
		nxt[i] = j;
	}
	ans2 = c - nxt[c];
	cout << ans * ans2;
	return 0;
}