#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
//const ll mod = 1e9+7;
bool maximize(int &x, int y ){
if (x <= y) {x = y; return true;};
return false;
}
bool minimize(ll &x, ll y){
if (x > y) {x = y; return true;}
return false;
}
//void add(ll &x, ll y ){
// x += y;
// if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
// x -= y;
// if (x < 0) x += mod;
//}
const int maxn = 3005;
int ans = 0, st1, st2, kmp1[maxn], kmp2[maxn], match1[maxn], match2[maxn];
void KMP(string &s, string &t, int kmp[], int match[]) {
int n = s.size(), m = t.size();
s = '0' + s;
t = '0' + t;
// cout << s << ' ' << t << "\n";
int las;
kmp[1] = las = 0;
for (int i = 2; i <= n; i++) {
while (las > 0 && s[i] != s[las+1]) las = kmp[las];
kmp[i] = s[i] == s[las+1] ? ++las : 0;
// cout << kmp[i] << ' ';
}
// cout << "\n";
kmp[0] = las = 0;
for (int i = 1; i <= m; i++) {
while (las > 0 && t[i] != s[las+1]) las = kmp[las];
match[i] = t[i] == s[las+1] ? ++las : 0;
// cout << match[i] << ' ';
}
// cout << "\n";
}
void solve(string &a, string &b, bool rev) {
int n = a.size(), m = b.size();
for (int i = 0; i < n; i++) {
string s1 = a.substr(0, i), s2 = a.substr(i, n-1);
string t1 = b, t2 = b;
reverse(s1.begin(), s1.end());
reverse(t1.begin(), t1.end());
KMP(s1, t1, kmp1, match1);
KMP(s2, t2, kmp2, match2);
//xuly :D
//match 1: dao, match 2: giu nguyen
// cout << s1 << ' ' << s2 << ' ' << t1 << ' ' << t2 << "\n";
for (int j = 1; j <= m; j++) {
int tempans = match2[j] + match1[m-j];
// cout << j << ' ' << tempans << ' ' << match1[m-j] << ' ' << match2[j] << ' ' << "\n";
if (maximize(ans, tempans)) {
st2 = j-match1[m-j];
st1 = i-match1[m-j];
if (rev) {
st2 = m-(j+match2[j]);
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string a, b;
cin >> a >> b;
solve(a, b, 0);
reverse(b.begin(), b.end());
solve(a, b, 1);
cout << ans << "\n" << st1 << ' ' << st2;
}
/*
zxyabcd
yxbadctz
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
