#include<bits/stdc++.h>
using namespace std;
const int maxN=1e6+5;
#define ll int
#define ben(x) x.begin(),x.end()
string s,t;
ll ans[3],n,m,p1[maxN+1],p2[maxN+1];
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()
{
cin>>s>>t;
n=s.length(),m=s.length();
solve(s,t,0);
reverse(ben(t));
solve(s,t,1);
cout<<ans[0]<<'\n'<<ans[1]<<" "<<ans[2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
2608 KB |
Output is correct |
| 2 |
Correct |
109 ms |
2608 KB |
Output is correct |
| 3 |
Correct |
167 ms |
2396 KB |
Output is correct |
| 4 |
Incorrect |
109 ms |
2600 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
