#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=0; 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=kmp[gh-1];
}
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=0; 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=kmp[gh-1];
}
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:36:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int l=0; l<k.size(); l++) kmp[l]=j;
| ~^~~~~~~~~
necklace.cpp:38:39: 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 x=tmp*2; x<k.size(); x++)
| ~^~~~~~~~~
necklace.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(tmp<=p&&tmp<=t.size())
| ~~~^~~~~~~~~~
necklace.cpp:88:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int l=0; l<k.size(); l++) kmp[l]=j;
| ~^~~~~~~~~
necklace.cpp:90:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int x=tmp*2; x<k.size(); x++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
9 ms |
212 KB |
Output is partially correct |
| 2 |
Partially correct |
9 ms |
320 KB |
Output is partially correct |
| 3 |
Correct |
9 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
212 KB |
Output is correct |
| 5 |
Correct |
7 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
9 ms |
212 KB |
Output is partially correct |
| 2 |
Partially correct |
9 ms |
320 KB |
Output is partially correct |
| 3 |
Correct |
9 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
212 KB |
Output is correct |
| 5 |
Correct |
7 ms |
212 KB |
Output is correct |
| 6 |
Correct |
635 ms |
316 KB |
Output is correct |
| 7 |
Partially correct |
806 ms |
316 KB |
Output is partially correct |
| 8 |
Correct |
735 ms |
316 KB |
Output is correct |
| 9 |
Correct |
711 ms |
316 KB |
Output is correct |
| 10 |
Correct |
562 ms |
212 KB |
Output is correct |
| 11 |
Correct |
452 ms |
432 KB |
Output is correct |
| 12 |
Correct |
693 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
9 ms |
212 KB |
Output is partially correct |
| 2 |
Partially correct |
9 ms |
320 KB |
Output is partially correct |
| 3 |
Correct |
9 ms |
212 KB |
Output is correct |
| 4 |
Correct |
12 ms |
212 KB |
Output is correct |
| 5 |
Correct |
7 ms |
212 KB |
Output is correct |
| 6 |
Correct |
635 ms |
316 KB |
Output is correct |
| 7 |
Partially correct |
806 ms |
316 KB |
Output is partially correct |
| 8 |
Correct |
735 ms |
316 KB |
Output is correct |
| 9 |
Correct |
711 ms |
316 KB |
Output is correct |
| 10 |
Correct |
562 ms |
212 KB |
Output is correct |
| 11 |
Correct |
452 ms |
432 KB |
Output is correct |
| 12 |
Correct |
693 ms |
316 KB |
Output is correct |
| 13 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
