#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
string s;
string t;
string s1,s2;
int L[3003],R[3003],dp1[3003],dp2[3003],m,n,k,cs1,cs2;
int maxx;
int riel(int x)
{
return t.size()-1-x;
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>s;
cin>>t;
for (int i=0;i<s.size();++i)
{
s1=" ";
s2=" ";
for (int j=i;j>=0;--j) s1+=s[j];
for (int j=i+1;j<s.size();++j) s2+=s[j];
L[1]=0;
k=0;
m=s1.size()-1;
n=s2.size()-1;
for (int j=2;j<=m;++j)
{
while (k>0 && s1[j]!=s1[k+1]) k=L[k];
if (s1[j]==s1[k+1]) L[j]=++k;
else L[j]=0;
}
k=0;
R[1]=0;
for (int j=2;j<=n;++j)
{
while (k>0 && s2[j]!=s2[k+1]) k=R[k];
if (s2[j]==s2[k+1]) R[j]=++k;
else R[j]=0;
}
k=0;
for (int j=0;j<t.size();++j)
{
while (k>0 && t[j]!=s2[k+1]) k=R[k];
if (t[j]==s2[k+1]) dp1[j]=++k;
else dp1[j]=0;
}
k=0;
for (int j=t.size()-1;j>=0;--j)
{
while (k>0 && t[j]!=s1[k+1]) k=L[k];
if (t[j]==s1[k+1]) dp2[j]=++k;
else dp2[j]=0;
}
for (int j=0;j<t.size();++j)
{
if (maxx<dp1[j]+dp2[j+1])
{
maxx=dp1[j]+dp2[j+1];
cs1=i-dp2[j+1]+1;
cs2=j-dp1[j]+1;
}
}
}
reverse(t.begin(),t.end());
for (int i=0;i<s.size();++i)
{
s1=" ";
s2=" ";
for (int j=i;j>=0;--j) s1+=s[j];
for (int j=i+1;j<s.size();++j) s2+=s[j];
L[1]=0;
k=0;
m=s1.size()-1;
n=s2.size()-1;
for (int j=2;j<=m;++j)
{
while (k>0 && s1[j]!=s1[k+1]) k=L[k];
if (s1[j]==s1[k+1]) L[j]=++k;
else L[j]=0;
}
k=0;
R[1]=0;
for (int j=2;j<=n;++j)
{
while (k>0 && s2[j]!=s2[k+1]) k=R[k];
if (s2[j]==s2[k+1]) R[j]=++k;
else R[j]=0;
}
k=0;
for (int j=0;j<t.size();++j)
{
while (k>0 && t[j]!=s2[k+1]) k=R[k];
if (t[j]==s2[k+1]) dp1[j]=++k;
else dp1[j]=0;
}
k=0;
for (int j=t.size()-1;j>=0;--j)
{
while (k>0 && t[j]!=s1[k+1]) k=L[k];
if (t[j]==s1[k+1]) dp2[j]=++k;
else dp2[j]=0;
}
for (int j=0;j<t.size();++j)
{
if (maxx<dp1[j]+dp2[j+1])
{
maxx=dp1[j]+dp2[j+1];
cs1=i-dp2[j+1]+1;
cs2=t.size()-1-(j+dp2[j+1]);
//cout<<dp1[j]<<" "<<dp2[j+1]<<" "<<j<<'\n';
}
}
}
cout<<maxx<<'\n';
cout<<cs1<<" "<<cs2;
//cout<<dp2[6]<<" "<<dp1[5];
}
Compilation message
necklace.cpp:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
15 | main()
| ^~~~
necklace.cpp: In function 'int main()':
necklace.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i=0;i<s.size();++i)
| ~^~~~~~~~~
necklace.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int j=i+1;j<s.size();++j) s2+=s[j];
| ~^~~~~~~~~
necklace.cpp:46:23: 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 j=0;j<t.size();++j)
| ~^~~~~~~~~
necklace.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j=0;j<t.size();++j)
| ~^~~~~~~~~
necklace.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i=0;i<s.size();++i)
| ~^~~~~~~~~
necklace.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int j=i+1;j<s.size();++j) s2+=s[j];
| ~^~~~~~~~~
necklace.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int j=0;j<t.size();++j)
| ~^~~~~~~~~
necklace.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int j=0;j<t.size();++j)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
255 ms |
508 KB |
Output is correct |
| 2 |
Correct |
224 ms |
344 KB |
Output is correct |
| 3 |
Correct |
301 ms |
512 KB |
Output is correct |
| 4 |
Correct |
232 ms |
344 KB |
Output is correct |
| 5 |
Correct |
117 ms |
344 KB |
Output is correct |
| 6 |
Correct |
125 ms |
504 KB |
Output is correct |
| 7 |
Correct |
175 ms |
600 KB |
Output is correct |
| 8 |
Correct |
206 ms |
500 KB |
Output is correct |
| 9 |
Correct |
223 ms |
492 KB |
Output is correct |
