Submission #992159

#	Time	Username	Problem	Language	Result	Execution time	Memory
992159		Catas	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	183 ms	604 KiB

necklace

#include <bits/stdc++.h>

#define ll long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(b) for(ll i = 0; i<b; i++)
#define repn(a, b) for(ll b = 0; i<a; i++)
#define LSOne(S) (S & -(S))
#define mem(a, b) memset(a, b, sizeof(a))
#define MOD 1000000007ll
#define MAXN 6002

using namespace std;

void suffix_array(string const& s, vector<ll>& p, vector<ll>& lcp) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> c(n), cnt(max(alphabet, n), 0);
    for (int i = 0; i < n; i++)
        cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++)
        cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++)
        p[--cnt[s[i]]] = i;
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]])
            classes++;
        c[p[i]] = classes - 1;
    }
    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0)
                pn[i] += n;
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++)
            cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++)
            cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--)
            p[--cnt[c[pn[i]]]] = pn[i];
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev)
                ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }

    int k = 0;
    for(int i = 0; i < n-1; i++){
        int pi = c[i];
        int j = p[pi-1];

        while(s[i+k] == s[j+k]) k++;
        lcp[pi] = k;
        k = max(k-1, 0);
    }
}

int pi1[MAXN], pi2[MAXN];

void kmp(string s, int* pi){
    pi[0] = 0;
    int len = 0, j = 1, m = s.size();
    while(j<m){
        if(s[j] == s[len]){
            pi[j] = ++len;
            j++;
        }
        else{
            if(len) len = pi[len-1];
            else{
                pi[j] = 0;
                j++;
            }
        }
    }
}

void solution(string s, string t, vector<int>& ans, bool rev){
    int n = s.size(), m = t.size();
    for(int i = 0; i < n; i++){
        string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
        reverse(s1.begin(), s1.end());

        string t1 = t, t2 = t;
        reverse(t2.begin(), t2.end());

        kmp(s1 + "#" + t1, pi1); kmp(s2 + "#" + t2, pi2);

        for(int j = 1; j<=m; j++){
            if(pi1[i + j] + pi2[n + m - i - j] > ans[0]){
                ans[0] = pi1[i+j] + pi2[n+m-i-j];
                ans[1] = i - pi1[i+j];
                ans[2] = rev ? m - j - pi2[n+m-i-j] : j - pi1[i+j];
            }
        }
    }
}

void solve(){
    string s, t;
    cin>>s>>t;
    vector<int> ans(3, 0);
    solution(s, t, ans, 0);
    reverse(t.begin(), t.end());
    solution(s, t, ans, 1);
    
    cout<<ans[0]<<'\n'<<ans[1]<<' '<<ans[2]<<'\n';
}   


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

• Subtask 1: 15 / 15