#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
string s, t; cin>>s>>t;
vector<int> kmp(400*5);
int ss=0;
int p=s.size();
array<int,3> ans={0, 0, 0};
s+=s;
for(int i=8; i>=0; i--)
{
int tmp=ss+(1<<i);
if(tmp<=p&&tmp<=t.size())
{
for(int l=0; l<=p-tmp; l++)
{
string k=s.substr(l, tmp);
k+=k;
k+=t;
for(int j=0; j<tmp; j++)
{
for(int l=i; l<k.size(); l++) kmp[l]=j;
for(int x=tmp*2; x<k.size(); x++)
{
int gh=kmp[x-1];
while(gh>j&&k[gh]!=k[x])
{
gh=k[gh-1];
break;
}
if(k[gh]==k[x])gh++;
kmp[x]=gh;
if(gh-j==tmp&&ans[0]!=tmp)
{
ans[0]=tmp;
ans[1]=l;
ans[2]=((x-tmp*3+1)%t.size()+t.size())%t.size();
}
}
}
}
if(ans[0]==tmp) ss=tmp;
}
}
auto ans1=ans;
ans={0, 0, 0};
ss=0;
reverse(s.begin(), s.end());
for(int i=8; i>=0; i--)
{
int tmp=ss+(1<<i);
if(tmp<=p&&tmp<=t.size())
{
for(int l=0; l<=p-tmp; l++)
{
string k=s.substr(l, tmp);
k+=k;
k+=t;
for(int j=0; j<tmp; j++)
{
for(int l=i; l<k.size(); l++) kmp[l]=j;
for(int x=tmp*2; x<k.size(); x++)
{
int gh=kmp[x-1];
while(gh>j&&k[gh]!=k[x])
{
gh=k[gh-1];
break;
}
if(k[gh]==k[x])gh++;
kmp[x]=gh;
if(gh-j==tmp&&ans[0]!=tmp)
{
ans[0]=tmp;
ans[1]=((p-1)-(l+tmp-1));
ans[2]=((x-tmp*3+1)%t.size()+t.size())%t.size();
}
}
}
}
if(ans[0]==tmp) ss=tmp;
}
}
ans=max(ans1, ans);
cout<<ans[0]<<"\n"<<ans[1]<<" "<<ans[2];
}
Compilation message
necklace.cpp: In function 'int32_t main()':
necklace.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | if(tmp<=p&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:33:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int l=i; l<k.size(); l++) kmp[l]=j;
| ~^~~~~~~~~
necklace.cpp:35:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int x=tmp*2; x<k.size(); x++)
| ~^~~~~~~~~
necklace.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if(tmp<=p&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:87:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int l=i; l<k.size(); l++) kmp[l]=j;
| ~^~~~~~~~~
necklace.cpp:89:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int x=tmp*2; x<k.size(); x++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
