/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 20010;
string s, t;
int pf[maxn], pb[maxn], n, m;
int nxt[maxn], bef[maxn];
void solve_front(string s)
{
reverse(s.begin(), s.end());
for (int i = 1; i < s.size(); i ++)
{
int j = pf[i - 1];
while(j > 0 && s[j] != s[i])
j = pf[j - 1];
if (s[j] == s[i])
j ++;
pf[i] = j;
}
int to = 0;
for (int j = t.size() - 1; j >= 0; j --)
{
while(to > 0 && s[to] != t[j])
to = pf[to - 1];
if (s[to] == t[j])
to ++;
nxt[j] = to;
}
}
void solve_back(string s)
{
for (int i = 1; i < s.size(); i ++)
{
int j = pb[i - 1];
while(j > 0 && s[j] != s[i])
j = pb[j - 1];
if (s[j] == s[i])
j ++;
pb[i] = j;
}
int to = 0;
for (int j = 0; j < t.size(); j ++)
{
while(to > 0 && s[to] != t[j])
to = pb[to - 1];
if (s[to] == t[j])
to ++;
bef[j] = to;
}
}
void solve()
{
cin >> s >> t;
n = s.size();
m = t.size();
int ans = 0, p1 = -1, p2 = -1;
for (int i = 0; i < n; i ++)
{
string ft = s.substr(0, i);
solve_front(ft);
string bk = s.substr(i, n);
solve_back(bk);
for (int j = 0; j < m; j ++)
{
int sum = nxt[j];
if (j != 0)
sum = sum + bef[j - 1];
if (sum > ans)
{
ans = sum;
///cout << i << " : " << j << " " << bef[j - 1] << " " << nxt[j] << endl;
p1 = i - nxt[j] + 1;
p2 = j + 1;
if (j != 0)
p2 = p2 - bef[j - 1];
}
}
}
reverse(t.begin(), t.end());
for (int i = 0; i < n; i ++)
{
string ft = s.substr(0, i);
solve_front(ft);
string bk = s.substr(i, n);
solve_back(bk);
for (int j = 0; j < m; j ++)
{
int sum = nxt[j];
if (j != 0)
sum = sum + bef[j - 1];
if (sum > ans)
{
ans = sum;
///cout << i << " : " << j << " " << bef[j - 1] << " " << nxt[j] << endl;
p1 = i - nxt[j] + 1;
p2 = j + 1;
if (j != 0)
p2 = p2 - bef[j - 1];
p2 = m - p2 + 1;
p2 = p2 - sum + 1;
}
}
}
reverse(t.begin(), t.end());
//string s1 = s.substr(p1 - 1, ans);
//string s2 = t.substr(p2 - 1, ans);
///cout << s1 << " " << s2 << endl;
if (ans == 0)
{
cout << 0 << " " << endl << 0 << " " << 0 << endl;
return;
}
cout << ans << " " << endl << p1 - 1 << " " << p2 - 1 << endl;
}
int main()
{
///freopen("test.in", "r", stdin);
solve();
return 0;
}
/**
yxbadctz
*/
Compilation message
necklace.cpp: In function 'void solve_front(std::string)':
necklace.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 1; i < s.size(); i ++)
| ~~^~~~~~~~~~
necklace.cpp: In function 'void solve_back(std::string)':
necklace.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 1; i < s.size(); i ++)
| ~~^~~~~~~~~~
necklace.cpp:64:23: 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 = 0; j < t.size(); j ++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
404 KB |
Output is correct |
| 2 |
Correct |
164 ms |
424 KB |
Output is correct |
| 3 |
Correct |
221 ms |
380 KB |
Output is correct |
| 4 |
Correct |
151 ms |
420 KB |
Output is correct |
| 5 |
Correct |
121 ms |
340 KB |
Output is correct |
| 6 |
Correct |
136 ms |
432 KB |
Output is correct |
| 7 |
Correct |
147 ms |
436 KB |
Output is correct |
| 8 |
Correct |
169 ms |
392 KB |
Output is correct |
| 9 |
Correct |
174 ms |
428 KB |
Output is correct |
