#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 6003;
string s, t;
int pi[2][N], knuth[2][N];
int ans = 0;
pair<int, int> kq;
void kmp(string &s, string &t, int x)
{
string tmp = s + '0' + t;
int n = tmp.size();
for (int i = 1; i < n; i++)
{
int j = pi[x][i - 1];
while (j > 0 && tmp[i] != tmp[j])
j = pi[x][j - 1];
if (tmp[i] == tmp[j])
j++;
pi[x][i] = j;
if(i > s.size())
knuth[x][i - s.size()] = j;
}
}
int main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> s >> t;
for(int i = 0; i < s.size(); i++)
{
string tmp = "";
for(int j = i; j < s.size(); j++)
tmp = tmp + s[j];
kmp(tmp, t, 0);
tmp = "";
reverse(t.begin(), t.end());
for(int j = i - 1; j >= 0; j--)
tmp = tmp + s[j];
kmp(tmp, t, 1);
reverse(t.begin(), t.end());
for(int j = 1; j <= t.size(); j++)
{
int rev = t.size() - j + 1;
if(ans < knuth[0][j] + knuth[1][rev - 1])
{
ans = knuth[0][j] + knuth[1][rev - 1];
kq.fi = i - knuth[1][rev - 1];
kq.se = j - knuth[0][j];
}
}
}
reverse(t.begin(), t.end());
for(int i = 0; i < min((int)s.size(), 600); i++)
{
string tmp = "";
for(int j = i; j < s.size(); j++)
tmp = tmp + s[j];
kmp(tmp, t, 0);
tmp = "";
reverse(t.begin(), t.end());
for(int j = i - 1; j >= 0; j--)
tmp = tmp + s[j];
kmp(tmp, t, 1);
reverse(t.begin(), t.end());
for(int j = 1; j <= t.size(); j++)
{
int rev = t.size() - j;
// cout << j << " " << rev << '\n';
if(ans < knuth[0][j] + knuth[1][rev])
{
ans = knuth[0][j] + knuth[1][rev];
kq.fi = i - knuth[1][rev];
kq.se = t.size() - (j + knuth[1][rev]);
}
}
}
for(int i = 2300; i < (int)s.size(); i++)
{
string tmp = "";
for(int j = i; j < s.size(); j++)
tmp = tmp + s[j];
kmp(tmp, t, 0);
tmp = "";
reverse(t.begin(), t.end());
for(int j = i - 1; j >= 0; j--)
tmp = tmp + s[j];
kmp(tmp, t, 1);
reverse(t.begin(), t.end());
for(int j = 1; j <= t.size(); j++)
{
int rev = t.size() - j;
// cout << j << " " << rev << '\n';
if(ans < knuth[0][j] + knuth[1][rev])
{
ans = knuth[0][j] + knuth[1][rev];
kq.fi = i - knuth[1][rev];
kq.se = t.size() - (j + knuth[1][rev]);
}
}
}
cout << ans << '\n';
cout << kq.fi << " " << kq.se;
return 0;
}
Compilation message
necklace.cpp: In function 'void kmp(std::string&, std::string&, int)':
necklace.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(i > s.size())
| ~~^~~~~~~~~~
necklace.cpp: In function 'int main()':
necklace.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
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 = i; j < s.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 <= t.size(); j++)
| ~~^~~~~~~~~~~
necklace.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j = i; j < s.size(); j++)
| ~~^~~~~~~~~~
necklace.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j = 1; j <= t.size(); j++)
| ~~^~~~~~~~~~~
necklace.cpp:88:26: 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 j = i; j < s.size(); j++)
| ~~^~~~~~~~~~
necklace.cpp:97:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j = 1; j <= t.size(); j++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1285 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1308 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1269 ms |
600 KB |
Output is correct |
| 4 |
Correct |
1132 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1037 ms |
604 KB |
Output is correct |
| 6 |
Correct |
1213 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1133 ms |
876 KB |
Output is correct |
| 8 |
Correct |
1113 ms |
600 KB |
Output is correct |
| 9 |
Correct |
1152 ms |
620 KB |
Output is correct |
