#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
struct ans{
int l, a, b;
ans(int l, int a, int b):l(l), a(a), b(b){}
bool operator<(ans rhs)const{
return l<rhs.l;
}
};
vector<int> zalgo(const string& s){
if(s.empty())
return {0};
vector<int> ret(s.size());
ret[0]=0;
for(int i=1; i<s.size(); i++){
int& c=ret[i]=ret[i-1];
while(c and s[c]!=s[i])
c=ret[c];
c+=s[c]==s[i];
}
return ret;
}
ans solve(const string& s, const string& t){
vector<vector<int>> tz, sz;
tz.reserve(s.size()+1);
sz.reserve(t.size()+1);
for(int i=0; i<=s.size(); i++){
string u{s.begin()+i, s.end()};
u+=' ';
u+=t;
auto z=zalgo(u);
tz.push_back(vector<int>{z.begin()+(s.size()-i), z.end()});
}
for(int i=0; i<=t.size(); i++){
string u{t.begin()+i, t.end()};
u+=' ';
u+=s;
auto z=zalgo(u);
sz.push_back(vector<int>{z.begin()+(t.size()-i), z.end()});
}
ans ret(0, 0, 0);
for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
ret=max(ret, ans(sz[j][i]+tz[i][j], i-sz[j][i], j-tz[i][j]));
return ret;
}
int main(){
string s, t;
cin>>s>>t;
ans rec1=solve(s, t);
reverse(t.begin(), t.end());
ans rec2=solve(s, t);
rec2.b=t.size()-(rec2.b+rec2.l);
rec1=max(rec1, rec2);
printf("%d\n%d %d\n", rec1.l, rec1.a, rec1.b);
}
Compilation message
necklace.cpp: In function 'std::vector<int> zalgo(const string&)':
necklace.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=1; i<s.size(); i++){
| ~^~~~~~~~~
necklace.cpp: In function 'ans solve(const string&, const string&)':
necklace.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i=0; i<=s.size(); i++){
| ~^~~~~~~~~~
necklace.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0; i<=t.size(); i++){
| ~^~~~~~~~~~
necklace.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
| ~^~~~~~~~~~
necklace.cpp:47:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0; i<=s.size(); i++)for(int j=0; j<=t.size(); j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1580 ms |
204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
