제출 #1154335

#제출 시각아이디문제언어결과실행 시간메모리
1154335misavoNecklace (Subtask 4) (BOI19_necklace4)C++20
0 / 15
1595 ms320 KiB
#include <bits/stdc++.h>
// #include <iostream>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define sz(x) int((x).size())
#define all(a) begin(a), end(a)
#define pll pair<long long, long long>
#define vb vector<bool>
#define vll vector<long long>
#define vvll vector<vector<long long> >
#define vpl vector< pair<long long, long long> >
#define f(i,s,e) for(long long int i = s; i < e; i++)
#define cf(i,s,e) for(long long int i = s; i <= e; i++)
#define rf(i,s,e) for(long long int i = s; i >= e; i--)
#define print(a) for(auto x : a) cout << x <<  <<endl;
#define printp(a) for(auto x : a) cout << x.first <<  << x.second <<endl;
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

inline ll read() {ll x = 0, fh = 1; char ch = getchar(); while(!isdigit(ch)) {if (ch == '-') fh = -1; ch = getchar();} while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();} return x*fh;}

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

ll t, n, m, k, a, b, tot;
string s1, s2;
ll lps[3009];

void solve() {
    cin >> s1 >> s2;

    bool sw = false;
    if (s2.size() > s1.size()) {
        swap(s1, s2);
        sw = true;
    }

    f(i, 1, s1.size()) {
        ll len = lps[i-1];
        f(j, 0, i) if (s1[i] == s1[j]) len = j + 1;
        lps[i] = len;
    }

    // f(i, 0, s1.size()) cout << lps[i] << " ";
    // cout<<endl;

    vector<vll> chars(27, vll());
    f(i, 0, s1.size()) chars[s1[i] - 'a'].pb(i);

    ll i1, i2, ans = 0;
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        while (j < s2.size() && r <= s1.size() && l >= 0) {
            // cout << r << " " << j << endl;
            if (r < s1.size() && s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll start = temp, jj = j;
                        // cout << temp <<endl;
                        while (temp <= l && jj < s2.size()) {
                            // cout << jj << " " << temp <<endl;
                            if (temp == l && jj - i > ans) {
                                ans = jj - i;
                                i1 = start;
                                i2 = i;
                            }
                            if (temp != l && temp < s1.size() && s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    ll d = temp - start;
                                    temp = lps[temp - 1];
                                    start = temp - d;
                                } while (temp && s1[temp] != s2[jj]);
                                if (!temp) break;
                            }
                        }

                        // cout << jj << " " << temp <<endl;
                        if (temp == l && jj - i > ans) {
                            ans = jj - i;
                            i1 = start;
                            i2 = i;
                        }
                    } 
                }

                if (j - i > ans) {
                    ans = j - i;
                    i1 = l;
                    i2 = i;
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }  

        if (j - i > ans) {
            ans = j - i;
            i1 = l;
            i2 = i;
        }
    }

    reverse(all(s2));
    f(i, 0, s2.size()) {
        if (chars[s2[i] - 'a'].empty()) continue;
        ll l = chars[s2[i] - 'a'].back();
        ll j = i, r = l;
        while (j < s2.size() && r <= s1.size() && l >= 0) {
            if (r < s1.size() && s1[r] == s2[j]) {
                j++; r++;
            } else {
                if (!chars[s2[j] - 'a'].empty()) {
                    ll back = lower_bound(all(chars[s2[j] - 'a']), l) - chars[s2[j] - 'a'].begin() - 1;
                    if (back != -1) {
                        ll temp = chars[s2[j] - 'a'][back];
                        ll start = temp, jj = j;
                        while (temp <= l && jj < s2.size()) {
                            if (temp == l && jj - i > ans) {
                                ans = jj - i;
                                i1 = start;
                                i2 = s2.size() - jj;
                            }
                            if (temp != l && temp < s1.size() && s1[temp] == s2[jj]) {
                                temp++; jj++;
                            } else {
                                if (!temp) break;
                                do {
                                    ll d = temp - start;
                                    temp = lps[temp - 1];
                                    start = temp - d;
                                } while (temp && s1[temp] != s2[jj]);
                                if (!temp) break;
                            }
                        }
                        // cout << i << " " << jj - i <<endl;
                        if (temp == l && jj - i > ans) {
                            ans = jj - i;
                            i1 = start;
                            i2 = s2.size() - jj;
                        }
                    } 
                }
                
                if (j - i > ans) {
                    ans = j - i;
                    i1 = l;
                    i2 = s2.size() - j;
                }

                do {
                    r = lps[r - 1];
                } while (r && s1[r] != s2[j]);
                l = r - (j - i);
            }
        }

        if (j - i > ans) {
            ans = j - i;
            i1 = l;
            i2 = s2.size() - j;
        }
    }
    cout << ans <<endl;
    if (sw) cout << i2 << " " << i1 <<endl;
    else cout << i1 << " " << i2 <<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    t = 1;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...