记录

O(n^3)会T爆

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
const int BASE = 29; // 哈希函数的基数
const long long MOD = 1e9 + 7; // 哈希函数的模数

int n, m;
char a[MAXN][MAXN];
long long pow_base[MAXN]; // pow_base[i] = BASE^i % MOD
vector<vector<long long>> hash_diag1, hash_diag2; // 预处理对角线的哈希值

// 计算字符串 s 的哈希值
long long get_hash(const string& s) {
  long long hash_val = 0;
  for (int i = 0; i < s.size(); ++i) {
    hash_val = (hash_val * BASE + s[i]) % MOD;
  }
  return hash_val;
}

// 判断以 (i, j) 为左上角，边长为 len 的正方形是否为“内存杀手”
bool check(int i, int j, int len) {
  if (i + len > n || j + len > m) {
    return false;
  }
  // 检查主对角线
  long long hash1 = (hash_diag1[i + len - 1][j + len - 1] - hash_diag1[i - 1][j - 1] * pow_base[len] % MOD + MOD) % MOD;
  long long hash2 = (hash_diag1[i + len - 1][j] - hash_diag1[i - 1][j - len] * pow_base[len] % MOD + MOD) % MOD;
  if (hash1 != hash2) {
    return false;
  }
  // 检查副对角线
  hash1 = (hash_diag2[i + len - 1][j] - hash_diag2[i - 1][j - len] * pow_base[len] % MOD + MOD) % MOD;
  hash2 = (hash_diag2[i + len - 1][j + len - 1] - hash_diag2[i - 1][j - 1] * pow_base[len] % MOD + MOD) % MOD;
  if (hash1 != hash2) {
    return false;
  }
  return true;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  // 预处理 BASE 的幂次
  pow_base[0] = 1;
  for (int i = 1; i <= max(n, m); ++i) {
    pow_base[i] = pow_base[i - 1] * BASE % MOD;
  }
  // 预处理对角线的哈希值
  hash_diag1 = vector<vector<long long>>(n + 1, vector<long long>(m + 1, 0));
  hash_diag2 = vector<vector<long long>>(n + 1, vector<long long>(m + 1, 0)); 
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      hash_diag1[i][j] = (hash_diag1[i - 1][j - 1] * BASE + a[i - 1][j - 1]) % MOD;
      if (j < m) { // 修正：边界检查
        hash_diag2[i][j] = (hash_diag2[i - 1][j + 1] * BASE + a[i - 1][j - 1]) % MOD;
      }
    }
  }
  int ans = -1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int len = 2; i + len <= n && j + len <= m; ++len) {
        if (check(i, j, len)) {
          ans = max(ans, len);
        }
      }
    }
  }
  cout << ans << endl; // 输出最大边长
  return 0;
}