#include <bits/stdc++.h>
using namespace std;
const long long mult=31;
const long long mod=1e9+7;
string a,b;
long long p[3001];
long long h[3001][3001];
long long f[401][401][401];
map<long long,pair<long long,long long> > mp;
void prec()
{
p[0]=1;
for(long long i=1; i<=a.size(); i++)
p[i]=(p[i-1]*mult)%mod;
for(long long i=0; i<a.size(); i++)
{
h[i][i]=((a[i]-'a'+1)*mult)%mod;
//cout<<a[i]<<" "<<h[i][i]<<endl;
mp[h[i][i]]= {i+1,i+1};
for(long long j=i+1; j<a.size(); j++)
{
h[i][j]=((h[i][j-1]+(a[j]-'a'+1))*mult)%mod;
mp[h[i][j]]= {i+1,j+1};
}
}
for(long long i=0; i<a.size(); i++)
{
for(long long j=i; j<a.size(); j++)
{
for(long long k=0; k<i; k++)
{
f[i][j][k]=(h[i][j]*p[i-k]+h[k][i-1])%mod;
//cout<<f[i][j][k]<<endl;
mp[f[i][j][k]]= {k+1,j+1};
}
}
}
reverse(a.begin(),a.end());
for(long long i=0; i<a.size(); i++)
{
h[i][i]=((a[i]-'a'+1)*mult)%mod;
//cout<<a[i]<<" "<<h[i][i]<<endl;
mp[h[i][i]]= {a.size()-i,a.size()-i};
for(long long j=i+1; j<a.size(); j++)
{
h[i][j]=((h[i][j-1]+(a[j]-'a'+1))*mult)%mod;
mp[h[i][j]]= {a.size()-j,a.size()-i};
}
}
for(long long i=0; i<a.size(); i++)
{
for(long long j=i; j<a.size(); j++)
{
for(long long k=0; k<i; k++)
{
f[i][j][k]=(h[i][j]*p[i-k]+h[k][i-1])%mod;
//cout<<f[i][j][k]<<endl;
mp[f[i][j][k]]= {a.size()-j,a.size()-k};
}
}
}
}
void solve()
{
long long len=0,l=0,r=0;
for(long long i=0; i<b.size(); i++)
{
long long curr=0;
for(long long j=i; j<b.size(); j++)
{
curr=((curr+(b[j]-'a'+1))*mult)%mod;
//cout<<i<<" "<<j<<" "<<b[j]<<" "<<curr<<endl;
if(mp[curr].first!=0&&(j-i+1)>=len)
{
len=j-i+1;
l=mp[curr].first-1;
r=i;
}
}
}
cout<<len<<endl;
cout<<l<<" "<<r<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>a>>b;
prec();
solve();
return 0;
}
Compilation message
necklace.cpp: In function 'void prec()':
necklace.cpp:15:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(long long i=1; i<=a.size(); i++)
| ~^~~~~~~~~~
necklace.cpp:18:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(long long i=0; i<a.size(); i++)
| ~^~~~~~~~~
necklace.cpp:23:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(long long j=i+1; j<a.size(); j++)
| ~^~~~~~~~~
necklace.cpp:30:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(long long i=0; i<a.size(); i++)
| ~^~~~~~~~~
necklace.cpp:32:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(long long j=i; j<a.size(); j++)
| ~^~~~~~~~~
necklace.cpp:44:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(long long i=0; i<a.size(); i++)
| ~^~~~~~~~~
necklace.cpp:49:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(long long j=i+1; j<a.size(); j++)
| ~^~~~~~~~~
necklace.cpp:56:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(long long i=0; i<a.size(); i++)
| ~^~~~~~~~~
necklace.cpp:58:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(long long j=i; j<a.size(); j++)
| ~^~~~~~~~~
necklace.cpp: In function 'void solve()':
necklace.cpp:73:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(long long i=0; i<b.size(); i++)
| ~^~~~~~~~~
necklace.cpp:76:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(long long j=i; j<b.size(); j++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
141296 KB |
Output is correct |
| 2 |
Correct |
91 ms |
140244 KB |
Output is correct |
| 3 |
Correct |
33 ms |
106064 KB |
Output is correct |
| 4 |
Correct |
108 ms |
143836 KB |
Output is correct |
| 5 |
Incorrect |
163 ms |
149400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
141296 KB |
Output is correct |
| 2 |
Correct |
91 ms |
140244 KB |
Output is correct |
| 3 |
Correct |
33 ms |
106064 KB |
Output is correct |
| 4 |
Correct |
108 ms |
143836 KB |
Output is correct |
| 5 |
Incorrect |
163 ms |
149400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
141296 KB |
Output is correct |
| 2 |
Correct |
91 ms |
140244 KB |
Output is correct |
| 3 |
Correct |
33 ms |
106064 KB |
Output is correct |
| 4 |
Correct |
108 ms |
143836 KB |
Output is correct |
| 5 |
Incorrect |
163 ms |
149400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
