//BOI 2019 - Necklace
#include<bits/stdc++.h>
using namespace std;
int p1[6002], p2[6002];
string s1, s2;
pair<pair<int, int>, int> ans;
void KMP(string s, int* p)
{
int i, len;
for(i = 1; i < s.size(); i ++)
{
len = p[i - 1];
while(len && s[i] != s[len]) len = p[len - 1];
if(s[i] == s[len]) p[i] = len + 1;
else p[i] = 0;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
int i, j, lft, rgt;
cin>>s1>>s2;
string leftS2 = s2, rightS2 = s2;
reverse(leftS2.begin(), leftS2.end());
for(i = 0; i < s1.size(); i ++)
{
string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i);
reverse(leftS1.begin(), leftS1.end());
KMP(leftS1 + "#" + rightS2, p1);
KMP(rightS1 + "#" + leftS2, p2);
for(j = 1; j <= s2.size(); j ++)
{
ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, j - p1[i + j]});
//cout<<i<<" "<<j<<" : "<<p1[i + j]<<" "<<p2[s1.size() + s2.size() - i - j]<<endl;
//cout<<i<<" "<<j<<" : "<<j - p1[i + j]<<'\n';
}
}
//cout<<s2.size()<<endl;
reverse(s2.begin(), s2.end());
leftS2 = s2, rightS2 = s2;
reverse(leftS2.begin(), leftS2.end());
for(i = 0; i < s1.size(); i ++)
{
string leftS1 = s1.substr(0, i), rightS1 = s1.substr(i);
reverse(leftS1.begin(), leftS1.end());
//cout<<leftS1<<"#"<<rightS2<<" "<<rightS1<<"#"<<leftS2<<endl;
KMP(leftS1 + "#" + rightS2, p1);
KMP(rightS1 + "#" + leftS2, p2);
for(j = 1; j <= s2.size(); j ++)
{
ans = max(ans, {{p1[i + j] + p2[s1.size() + s2.size() - i - j], i - p1[i + j]}, s2.size() - j - p2[s1.size() + s2.size() - i - j]});
//cout<<i<<" "<<j<<" : "<<s2.size() - j - p2[s1.size() + s2.size() - i - j]<<'\n';
}
}
cout<<ans.first.first<<"\n"<<ans.first.second<<" "<<ans.second<<endl;
return 0;
}
Compilation message
necklace.cpp: In function 'void KMP(std::string, int*)':
necklace.cpp:10:18: 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(i = 1; i < s.size(); i ++)
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:26:18: 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(i = 0; i < s1.size(); i ++)
| ~~^~~~~~~~~~~
necklace.cpp:32:22: 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(j = 1; j <= s2.size(); j ++)
| ~~^~~~~~~~~~~~
necklace.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(i = 0; i < s1.size(); i ++)
| ~~^~~~~~~~~~~
necklace.cpp:51:22: 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(j = 1; j <= s2.size(); j ++)
| ~~^~~~~~~~~~~~
necklace.cpp:22:15: warning: unused variable 'lft' [-Wunused-variable]
22 | int i, j, lft, rgt;
| ^~~
necklace.cpp:22:20: warning: unused variable 'rgt' [-Wunused-variable]
22 | int i, j, lft, rgt;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
444 KB |
Output is correct |
| 2 |
Correct |
230 ms |
452 KB |
Output is correct |
| 3 |
Correct |
300 ms |
452 KB |
Output is correct |
| 4 |
Correct |
230 ms |
332 KB |
Output is correct |
| 5 |
Correct |
150 ms |
560 KB |
Output is correct |
| 6 |
Correct |
156 ms |
468 KB |
Output is correct |
| 7 |
Correct |
205 ms |
448 KB |
Output is correct |
| 8 |
Correct |
231 ms |
332 KB |
Output is correct |
| 9 |
Correct |
242 ms |
812 KB |
Output is correct |
