#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll P = 31;
const ll LOGN = 20;
const ll MAXN = 1e5 + 5;
int ans[3], n, m;
int p1[MAXN], p2[MAXN];
void compute(string s, int p_array[]) {
int q = s.length();
p_array[0] = 0;
for (int i = 1; i < q; i++) {
int j = p_array[i-1];
while (j && s[i] != s[j])
j = p_array[j-1];
if (s[i] == s[j])
j++;
p_array[i] = j;
}
}
void solve(string s, string t, bool rev) {
string t_rev = t;
reverse(t_rev.begin(), t_rev.end());
for (int i = 0; i < n; i++) {
string l_up = s.substr(0, i), r_up = s.substr(i, n);
reverse(l_up.begin(), l_up.end());
string for_a = l_up + "#" + t;
string for_b = r_up + "#" + t_rev;
compute(for_a, p1);
compute(for_b, p2);
for (int j = 1; j <= m; j++) {
int a = p1[i+j];
int b = p2[n+m-i-j];
if (a + b > ans[0]) {
ans[0] = a + b;
ans[1] = i - p1[i+j];
ans[2] = (rev ? m - j - b : j - a);
}
}
}
}
int main() {
fast
string s, t;
cin >> s >> t;
n = s.size(), m = t.size();
solve(s, t, 0);
reverse(t.begin(), t.end());
solve(s, t, 1);
cout << ans[0] << "\n" << ans[1] << " " << ans[2] << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
3 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
3 ms |
348 KB |
Output is correct |
9 |
Correct |
3 ms |
348 KB |
Output is correct |
10 |
Correct |
2 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
124 ms |
604 KB |
Output is correct |
14 |
Correct |
94 ms |
604 KB |
Output is correct |
15 |
Correct |
176 ms |
592 KB |
Output is correct |
16 |
Correct |
123 ms |
568 KB |
Output is correct |
17 |
Correct |
65 ms |
548 KB |
Output is correct |
18 |
Correct |
73 ms |
600 KB |
Output is correct |
19 |
Correct |
95 ms |
604 KB |
Output is correct |
20 |
Correct |
111 ms |
596 KB |
Output is correct |
21 |
Correct |
118 ms |
600 KB |
Output is correct |