Submission #996844

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
996844	2024-06-11T10:30:21 Z	Mike_Vu	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	207 ms	604 KB

necklace

#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-i);
        string t1 = b, t2 = b;
        reverse(s1.begin(), s1.end());
        reverse(t2.begin(), t2.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 = match1[j] + match2[m-j];
//            cout << j << ' ' << tempans << ' ' << match1[m-j] << ' ' << match2[j] << ' ' << "\n";
            if (maximize(ans, tempans)) {
                st2 = j-match1[j];
                st1 = i-match1[j];
                if (rev) {
                    st2 = m-(j+match2[m-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
*/

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	604 KB	Output is correct
2	Correct	156 ms	576 KB	Output is correct
3	Correct	191 ms	596 KB	Output is correct
4	Correct	130 ms	592 KB	Output is correct
5	Correct	180 ms	592 KB	Output is correct
6	Correct	202 ms	600 KB	Output is correct
7	Correct	173 ms	604 KB	Output is correct
8	Correct	177 ms	592 KB	Output is correct
9	Correct	179 ms	600 KB	Output is correct