Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- //#define int long long
- #define ll long long
- gp_hash_table<ll, int> mp;
- int P=179,mod=1791791791;
- void calc(vector<int> &h,string &s){
- h.resize(s.size()+1,0);
- for(int i=1;i<=s.size();i++){
- h[i]=((ll)h[i-1]*P+(s[i-1]-'a'+1))%mod;
- }
- }
- void getP(vector<int> &p,int n){
- p.resize(n+1,1);
- for(int i=1;i<p.size();i++){
- p[i]=((ll)p[i-1]*P)%mod;
- }
- }
- int res(int l,int r,vector<int> &h,vector<int> &p){
- return ((ll)h[r+1]+mod-((ll)h[l]*p[r-l+1])%mod)%mod;
- }
- signed main() {
- ios::ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n,m;
- cin>>n>>m;
- vector<string> a(n);
- vector<vector<int> > h(n),sm(n+1,vector<int> (m+1,0));
- vector<int> p;
- for(int i=0;i<n;i++){
- cin>>a[i];
- calc(h[i],a[i]);
- for(int j=1;j<=m;j++){
- sm[i+1][j]=sm[i][j]+sm[i+1][j-1]-sm[i][j-1]+(a[i][j-1]-'a'+1);
- }
- }
- getP(p,max(n,m));
- vector<vector<int> > dp(n,vector<int> (m,0));
- int k;
- pair<int,int> ans1={-1,-1};
- pair<int,int> ans2={-1,-1};
- for(k=1;k<=min(n,m);k++){
- bool check=false;
- mp.clear();
- for(int i=0;i<n-k+1;i++){
- for(int j=0;j<m-k+1;j++){
- int r=j+k,b=i+k-1;
- int sum=sm[b][r]-sm[i][r]-sm[b][r-1]+sm[i][r-1];
- dp[i][j]=(((ll)dp[i][j]*P*P)%mod+(ll)res(j,j+k-1,h[i+k-1],p)+sum)%mod;
- int res=mp[dp[i][j]];
- if(res!=0){
- ans1=make_pair(res/1000,res%1000);
- ans2=make_pair(i+1,j+1);
- check=true;
- }
- mp[dp[i][j]]=(ll)((i+1)*1000+(j+1));
- }
- }
- if(!check){
- break;
- }
- }
- if(k-1==0){
- cout<<0;
- return 0;
- }
- cout<<k-1<<endl;
- cout<<ans1.first<<" "<<ans1.second<<endl;
- cout<<ans2.first<<" "<<ans2.second<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement