#include <bits/stdc++.h>
using namespace std;
int pi[6005];
int kmp1[3001], kmp2[3001];
pair <int, int> solve(string a, string b, bool ok)//size(a) < size(b)
{
pair <int, int> max1 = {0, 0};
for(int i = 0; i < b.size(); i++)
{
///rezolv
string s = "#" + b + "$" + a;
pi[1] = 0;
for(int j = 2; j < s.size(); j++)
{
pi[j] = pi[j - 1];
while(pi[j] && s[pi[j] + 1] != s[j])
pi[j] = pi[pi[j]];
if(s[pi[j] + 1] == s[j])
pi[j]++;
}
for(int j = 1; j <= a.size(); j++)
kmp1[j] = pi[j + 1 + b.size()];
string ca, cb;
ca = a;
cb = b;
reverse(ca.begin(), ca.end());
reverse(cb.begin(), cb.end());
s = "#" + cb + "$" + ca;
pi[1] = 0;
for(int j = 2; j < s.size(); j++)
{
pi[j] = pi[j - 1];
while(pi[j] && s[pi[j] + 1] != s[j])
pi[j] = pi[pi[j]];
if(s[pi[j] + 1] == s[j])
pi[j]++;
}
for(int j = 1; j <= a.size(); j++)
kmp2[a.size() - j + 1] = pi[j + 1 + b.size()];
/*cout << a << '\n' << b << '\n';
for(int j = 1; j <= a.size(); j++)
cout << kmp1[j] << " ";
cout << '\n';
for(int j = 1; j <= a.size(); j++)
cout << kmp2[j] << " ";
cout << '\n';*/
for(int j = 1; j < a.size(); j++)
if(kmp1[j] + kmp2[j + 1] > max1.first && ((ok == 0 && (b.size() - kmp2[j + 1] - i + b.size()) % b.size() + kmp1[j] + kmp2[j + 1] - 1 < b.size()) || (ok == 1 && (b.size() - 1 - (b.size() - kmp2[j + 1] - i + b.size()) % b.size() - (kmp1[j] + kmp2[j + 1]) + 1 + b.size()) % b.size() + kmp1[j] + kmp2[j + 1] - 1 < b.size())))
{
max1.first = kmp1[j] + kmp2[j + 1];
//cout << kmp1[j] + kmp2[j + 1] << " " << j <<'\n';
max1.second = (j - kmp1[j]) * 10000 + (b.size() - kmp2[j + 1] - i + b.size()) % b.size();
}
rotate(b.begin(), prev(b.end()), b.end());
}
return max1;
}
int main()
{
#ifdef HOME
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif // HOME
string a, b;
bool ok;
cin >> a >> b;
if(a.size() > b.size())
{
ok = 1;
swap(a, b);
}
pair <int, int> ans1 = solve(a, b, 0);
reverse(b.begin(), b.end());
pair <int, int> ans2 = solve(a, b, 1);
if(ans1.first > ans2.first)
{
cout << ans1.first << '\n';
if(ok == 0)
cout << ans1.second / 10000 << " " << ans1.second % 10000;
else
cout << ans1.second % 10000 << " " << ans1.second / 10000;
}
else
{
cout << ans2.first << '\n';
if(ok == 0)
cout << ans2.second / 10000 << " " << (b.size() - 1 - ans2.second % 10000 - ans2.first + 1 + b.size()) % b.size();
else
cout << (b.size() - 1 - ans2.second % 10000 - ans2.first + 1 + b.size()) % b.size() << " " << ans2.second / 10000;
}
return 0;
}
Compilation message
necklace.cpp: In function 'std::pair<int, int> solve(std::string, std::string, bool)':
necklace.cpp:10:22: 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(int i = 0; i < b.size(); i++)
| ~~^~~~~~~~~~
necklace.cpp:15:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int j = 2; j < s.size(); j++)
| ~~^~~~~~~~~~
necklace.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int j = 1; j <= a.size(); j++)
| ~~^~~~~~~~~~~
necklace.cpp:32:26: 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 j = 2; j < s.size(); j++)
| ~~^~~~~~~~~~
necklace.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 1; j <= a.size(); j++)
| ~~^~~~~~~~~~~
necklace.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int j = 1; j < a.size(); j++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
