#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
using pii=pair<ll,ll>;
ll ga[1510];
ll ha[1510];
ll gb[1510];
ll hb[1510];
set<pii> s;
ll p7[30];
ll p5[30];
const ll mod=9223372036854775783ll;
int res=0;
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
{
ll a=1,b=1;
for(int i=0;i<26;i++){
p7[i]=a;
p5[i]=b;
a*=7;
b*=5;
a%=mod;
}
}
string a,b;
cin>>a>>b;
if(a.size()>b.size())swap(a,b);
ga[0]=gb[0]=ha[0]=hb[0]=0;
ga[1]=p7['z'-a[0]];
ha[1]=p5[a[0]-'a'];
for(int i=1;i<a.size();i++){
ga[i+1]=ga[i]+p3['z'-a[i]];
ha[i+1]=ha[i]+p5[a[i]-'a'];
}
gb[1]=p7['z'-b[0]];
hb[1]=p5[b[0]-'a'];
for(int i=1;i<b.size();i++){
gb[i+1]=gb[i]+p3['z'-b[i]];
hb[i+1]=hb[i]+p5[b[i]-'a'];
}
if(10ll*a.size()*a.size()*b.size()<=2e9){
for(int i=1;i<a.size();i++){
for(int j=0;j+res<i;j++){
for(int k=i-j;k<b.size();k++){
if(ha[i]-ha[j]==hb[k]-hb[k-i+j]){
res=max(res,i-j);
break;
}
}
}
}
cout<<res;
return 0;
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j<i;j++){
ll x=ga[i]-ga[j];
ll y=ha[i]-ha[j];
s.insert(pii(x,y));
}
}
for(int i=(int)a.size()-1;i>0;i--){
for(int j=0;j+res<i;j++){
ll x=gb[i]-gb[j];
ll y=hb[i]-hb[j];
if(s.find(pii(x,y))!=s.end()){
res=max(res,i-j);
break;
}
}
}
cout<<res;
}
Compilation message
interval.cpp: In function 'int main()':
interval.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=1;i<a.size();i++){
| ~^~~~~~~~~
interval.cpp:41:17: error: 'p3' was not declared in this scope; did you mean 'p5'?
41 | ga[i+1]=ga[i]+p3['z'-a[i]];
| ^~
| p5
interval.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=1;i<b.size();i++){
| ~^~~~~~~~~
interval.cpp:47:17: error: 'p3' was not declared in this scope; did you mean 'p5'?
47 | gb[i+1]=gb[i]+p3['z'-b[i]];
| ^~
| p5
interval.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=1;i<a.size();i++){
| ~^~~~~~~~~
interval.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int k=i-j;k<b.size();k++){
| ~^~~~~~~~~
