fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i,a,b) for (auto i=(a); i<=(b); ++i)
  8. #define ffr(i,b,a) for (auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define pb emplace_back
  11. #define fi first
  12. #define se second
  13. #define all(s) (s).begin(), (s).end()
  14. #define ms(a,x) memset(a, x, sizeof(a))
  15. #define re exit(0)
  16.  
  17. typedef long long ll;
  18. typedef pair<ll,ll> pll;
  19. typedef vector<ll> vll;
  20. typedef vector<pll> vpll;
  21.  
  22. const int maxn = 105;
  23. const int base = 256;
  24. const int MOD1 = 998244353;
  25. const int MOD2 = 1000000007;
  26.  
  27. int n, m;
  28. char a[maxn][maxn], b[maxn][maxn];
  29. pll p[maxn*maxn], invp[maxn*maxn];
  30. pll s[2][maxn][maxn];
  31.  
  32. inline int id(int i, int j){ return (i-1)*m + j; }
  33.  
  34. ll bpow(ll a, ll b, ll mod){
  35.     ll res=1;
  36.     while(b){
  37.         if(b&1) res=res*a%mod;
  38.         a=a*a%mod;
  39.         b>>=1;
  40.     }
  41.     return res;
  42. }
  43.  
  44. pll operator+(pll A, pll B){ return {(A.fi+B.fi)%MOD1, (A.se+B.se)%MOD2}; }
  45. pll operator-(pll A, pll B){ return {(A.fi-B.fi+MOD1)%MOD1, (A.se-B.se+MOD2)%MOD2}; }
  46. pll operator*(pll A, pll B){ return {A.fi*B.fi%MOD1, A.se*B.se%MOD2}; }
  47. pll operator*(pll A, ll k){ return {A.fi*k%MOD1, A.se*k%MOD2}; }
  48.  
  49. void pre(){
  50.     int lim = 100*100+5;
  51.     ll inv1 = bpow(base, MOD1-2, MOD1);
  52.     ll inv2 = bpow(base, MOD2-2, MOD2);
  53.     p[0] = {1,1};
  54.     invp[0] = {1,1};
  55.     ff(i,1,lim){
  56.         p[i] = {p[i-1].fi*base%MOD1, p[i-1].se*base%MOD2};
  57.         invp[i] = {invp[i-1].fi*inv1%MOD1, invp[i-1].se*inv2%MOD2};
  58.     }
  59. }
  60.  
  61. inline pll get(int t, int x, int y, int u, int v){
  62.     pll ans = s[t][u][v];
  63.     ans = ans + s[t][x-1][y-1];
  64.     ans = ans - s[t][x-1][v];
  65.     ans = ans - s[t][u][y-1];
  66.     ans = ans * invp[id(x, y)];
  67.     return ans;
  68. }
  69.  
  70. inline bool check(int r, int c){
  71.     vpll v;
  72.     ff(i,1,n-r+1) ff(j,1,m-c+1)
  73.         v.pb(get(0,i,j,i+r-1,j+c-1));
  74.     sort(all(v)); v.erase(unique(all(v)), v.end());
  75.     ff(i,1,n-r+1) ff(j,1,m-c+1){
  76.         pll cur = get(1,i,j,i+r-1,j+c-1);
  77.         if(binary_search(all(v), cur)) return 1;
  78.     }
  79.     return 0;
  80. }
  81.  
  82. signed main(){
  83.     ios::sync_with_stdio(false);
  84.     cin.tie(nullptr);
  85.     if(fopen(file".inp","r")){
  86.         freopen(file".inp","r",stdin);
  87.         freopen(file".out","w",stdout);
  88.     }
  89.     pre();
  90.     int tt; cin >> tt;
  91.     while(tt--){
  92.         cin >> n >> m;
  93.         ff(i,1,n) ff(j,1,m) cin >> a[i][j];
  94.         ff(i,1,n) ff(j,1,m) cin >> b[i][j];
  95.         ff(t,0,1) ff(i,0,n) ff(j,0,m) s[t][i][j] = {0,0};
  96.         ff(i,1,n) ff(j,1,m){
  97.             s[0][i][j] = s[0][i-1][j] + s[0][i][j-1] - s[0][i-1][j-1] + p[id(i,j)] * a[i][j];
  98.             s[0][i][j].fi%=MOD1; s[0][i][j].se%=MOD2;
  99.             s[1][i][j] = s[1][i-1][j] + s[1][i][j-1] - s[1][i-1][j-1] + p[id(i,j)] * b[i][j];
  100.             s[1][i][j].fi%=MOD1; s[1][i][j].se%=MOD2;
  101.         }
  102.         int c=m, ans=0;
  103.         ff(r,1,n){
  104.             while(c>0 && !check(r,c)) --c;
  105.             ans = max(ans, r*c);
  106.         }
  107.         cout << ans << nl;
  108.     }
  109.     re;
  110. }
  111.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2
9 8
bbbbbbbb
babbbbbb
aaaababb
bbbaaaab
abbbbbaa
bbbbbbba
abbaabbb
aaaaaaba
baabbaaa
bbbbbbbb
aabbabbb
aaabaaab
bbaabaab
bbbbbbbb
aabbbaba
aaaaaaaa
bbaaabbb
bbbbbaba
9 8
bbbbabab
bbbbbabb
bbbababa
bbbbabba
babbbbba
babbbabb
baaabaab
bbbaabba
baaabbbb
bbbbabaa
bbbbbaba
bbabbbab
bbbababa
bbababbb
bbbabbbb
abbbbaba
abbbabaa
aaabaabb
stdout
copy 
18
25
https://ideone.com/rrPDj0
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!