Advertisement
Gornak40

Govno

Mar 1st, 2021
662
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. //#define int long long
  8. #define ll long long
  9. gp_hash_table<ll, int> mp;
  10.  
  11. int P=179,mod=1791791791;
  12.  
  13. void calc(vector<int> &h,string &s){
  14.     h.resize(s.size()+1,0);
  15.  
  16.     for(int i=1;i<=s.size();i++){
  17.         h[i]=((ll)h[i-1]*P+(s[i-1]-'a'+1))%mod;
  18.     }
  19. }
  20.  
  21. void getP(vector<int> &p,int n){
  22.     p.resize(n+1,1);
  23.  
  24.     for(int i=1;i<p.size();i++){
  25.         p[i]=((ll)p[i-1]*P)%mod;
  26.     }
  27. }
  28.  
  29. int res(int l,int r,vector<int> &h,vector<int> &p){
  30.     return ((ll)h[r+1]+mod-((ll)h[l]*p[r-l+1])%mod)%mod;
  31. }
  32.  
  33. signed main() {
  34.  
  35.     ios::ios_base::sync_with_stdio(false);
  36.     cin.tie(0);
  37.     cout.tie(0);
  38.  
  39.     int n,m;
  40.     cin>>n>>m;
  41.  
  42.     vector<string> a(n);
  43.     vector<vector<int> > h(n),sm(n+1,vector<int> (m+1,0));
  44.     vector<int> p;
  45.  
  46.     for(int i=0;i<n;i++){
  47.         cin>>a[i];
  48.         calc(h[i],a[i]);
  49.         for(int j=1;j<=m;j++){
  50.             sm[i+1][j]=sm[i][j]+sm[i+1][j-1]-sm[i][j-1]+(a[i][j-1]-'a'+1);
  51.         }
  52.     }
  53.  
  54.     getP(p,max(n,m));
  55.  
  56.     vector<vector<int> > dp(n,vector<int> (m,0));
  57.     int k;
  58.     pair<int,int> ans1={-1,-1};
  59.     pair<int,int> ans2={-1,-1};
  60.     for(k=1;k<=min(n,m);k++){
  61.         bool check=false;
  62.         mp.clear();
  63.         for(int i=0;i<n-k+1;i++){
  64.             for(int j=0;j<m-k+1;j++){
  65.                 int r=j+k,b=i+k-1;
  66.                 int sum=sm[b][r]-sm[i][r]-sm[b][r-1]+sm[i][r-1];
  67.                 dp[i][j]=(((ll)dp[i][j]*P*P)%mod+(ll)res(j,j+k-1,h[i+k-1],p)+sum)%mod;
  68.                 int res=mp[dp[i][j]];
  69.                 if(res!=0){
  70.                     ans1=make_pair(res/1000,res%1000);
  71.                     ans2=make_pair(i+1,j+1);
  72.                     check=true;
  73.                 }
  74.                 mp[dp[i][j]]=(ll)((i+1)*1000+(j+1));
  75.             }
  76.         }
  77.  
  78.         if(!check){
  79.             break;
  80.         }
  81.     }
  82.  
  83.     if(k-1==0){
  84.         cout<<0;
  85.         return 0;
  86.     }
  87.     cout<<k-1<<endl;
  88.     cout<<ans1.first<<" "<<ans1.second<<endl;
  89.     cout<<ans2.first<<" "<<ans2.second<<endl;
  90.  
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement