#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=3499999991;
int n,m,ans,l,r;
ll hsh[2][3050],prec[3050];
string a,b;
map<string,int> hv;
void computehash(int id,string str){
for (int i=1;i<str.length();i++){
hsh[id][i]=hsh[id][i-1]*27+str[i]-'a'+1;
hsh[id][i]%=MOD;
}
}
string gethash(int id,int l,int r){
string ret="";
if (id) for (int i=l+1;i<=r;i++) ret+=b[i];
else for (int i=l+1;i<=r;i++) ret+=a[i];
return ret;
}
int main(){
cin>>a>>b;
a=' '+a;
b=' '+b;
computehash(0,a);
computehash(1,b);
prec[0]=1;
for (int i=1;i<=3000;i++) prec[i]=prec[i-1]*27%MOD;
for (int i=1;i<a.length();i++){
for (int j=i;j<a.length();j++){
for (int k=0;k<i;k++){
//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(0,i-1,j)*prec[i-k-1]+gethash(0,k,i-1))%MOD<<"\n";
hv[gethash(0,i-1,j)+gethash(0,k,i-1)]=k+1;
}
}
}
for (int i=1;i<b.length();i++){
for (int j=i;j<b.length();j++){
for (int k=0;k<i;k++){
//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(1,i-1,j)*prec[i-k-1]+gethash(1,k,i-1))%MOD<<"\n";
if (!hv[gethash(1,i-1,j)+gethash(1,k,i-1)]) continue;
if (j-k<ans) continue;
ans=j-k;
l=hv[gethash(1,i-1,j)+gethash(1,k,i-1)]-1;
r=k;
}
}
}
reverse(b.begin()+1,b.end());
computehash(1,b);
for (int i=1;i<b.length();i++){
for (int j=i;j<b.length();j++){
for (int k=0;k<i;k++){
//cout<<i<<"-"<<j<<"--"<<k<<"::"<<(gethash(1,i-1,j)*prec[i-k-1]+gethash(1,k,i-1))%MOD<<"\n";
if (!hv[gethash(1,i-1,j)+gethash(1,k,i-1)]) continue;
if (j-k<ans) continue;
ans=j-k;
l=hv[gethash(1,i-1,j)+gethash(1,k,i-1)]-1;
r=b.length()-1-j;
}
}
}
cout<<ans<<"\n"<<l<<" "<<r<<"\n";
}
Compilation message
necklace.cpp: In function 'void computehash(int, std::string)':
necklace.cpp:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i=1;i<str.length();i++){
| ~^~~~~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i=1;i<a.length();i++){
| ~^~~~~~~~~~~
necklace.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int j=i;j<a.length();j++){
| ~^~~~~~~~~~~
necklace.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i=1;i<b.length();i++){
| ~^~~~~~~~~~~
necklace.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int j=i;j<b.length();j++){
| ~^~~~~~~~~~~
necklace.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i=1;i<b.length();i++){
| ~^~~~~~~~~~~
necklace.cpp:52:17: 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 j=i;j<b.length();j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
30712 KB |
Output is correct |
| 2 |
Correct |
387 ms |
33760 KB |
Output is correct |
| 3 |
Correct |
264 ms |
19768 KB |
Output is correct |
| 4 |
Correct |
264 ms |
34180 KB |
Output is correct |
| 5 |
Correct |
411 ms |
74584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
30712 KB |
Output is correct |
| 2 |
Correct |
387 ms |
33760 KB |
Output is correct |
| 3 |
Correct |
264 ms |
19768 KB |
Output is correct |
| 4 |
Correct |
264 ms |
34180 KB |
Output is correct |
| 5 |
Correct |
411 ms |
74584 KB |
Output is correct |
| 6 |
Execution timed out |
1582 ms |
184024 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
30712 KB |
Output is correct |
| 2 |
Correct |
387 ms |
33760 KB |
Output is correct |
| 3 |
Correct |
264 ms |
19768 KB |
Output is correct |
| 4 |
Correct |
264 ms |
34180 KB |
Output is correct |
| 5 |
Correct |
411 ms |
74584 KB |
Output is correct |
| 6 |
Execution timed out |
1582 ms |
184024 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
