제출 #1306566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306566		veham	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	25 / 85	19 ms	8908 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
typedef short int shi;
typedef vector<shi> vi;
typedef vector<vi> vvi;
typedef map<shi,shi> mi;
typedef string str;
typedef pair<shi,pair<shi,shi>> pipi;

struct Node{
    shi idxs[26];
    shi backlink = -1;
    shi f;
    char c;
    vi d;
    Node(shi f, char c) : f(f), c(c) {
        for(shi i = 0;i < 26;i++) idxs[i] = -1;
    }
    Node(){}
};

struct Trie{
    vector<Node> nodes;
    Trie(){
        nodes.emplace_back(0,'#');
        nodes[0].backlink = 0;
    }

    void insert(str &S, shi s, shi e){
        shi curr = 0;
        for(shi i = s;i < e;i++){
            if(nodes[curr].idxs[S[i]-'a'] == -1) nodes[curr].idxs[S[i]-'a'] = nodes.size(),nodes.emplace_back(curr,S[i]);
            curr = nodes[curr].idxs[S[i]-'a'];
            nodes[curr].d.push_back(i);
        }
    }

    shi trans(shi v, char c){
        if(nodes[v].idxs[c-'a'] != -1) return nodes[v].idxs[c-'a'];
        if(v == 0) return nodes[v].idxs[c-'a'] = 0;
        return nodes[v].idxs[c-'a'] = trans(backlink(v),c);
    }

    shi backlink(shi v){
        if(nodes[v].backlink != -1) return nodes[v].backlink;
        if(nodes[v].f == 0) return nodes[v].backlink = 0;
        return nodes[v].backlink = trans(backlink(nodes[v].f), nodes[v].c);
    }
};

pipi calc_w_div(str &T, shi div, Trie &FS, Trie &BS, shi N, bool is_rev = 0){
    vi FL(N,0),BL(N,0);
    shi i,curr,prev;
    for(i = div,prev = curr = 0;i < T.size();i++){
        curr = FS.nodes[curr].idxs[T[i]-'a'];
        if(curr == -1) break;
        prev = curr;
    }
    set<shi> ds(FS.nodes[prev].d.begin(),FS.nodes[prev].d.end());
    vector<shi> vitr;
    for(shi k = 0;!ds.empty();k++){
        for(shi d : ds){
            if(d-k < 0){
                vitr.push_back(d);
                continue;
            }
            if(FL[d-k] >= i - div - k){
                vitr.push_back(d);
                continue;
            }
            FL[d-k] = i - div - k;
        }
        for(shi d : vitr) ds.erase(d);
        vitr.clear();
    }
    
    for(prev = curr = 0,i = div-1;i >= 0;i--){
        curr = BS.nodes[curr].idxs[T[i]-'a'];
        if(curr == -1) break;
        prev = curr;
    }
    ds = set<shi>(BS.nodes[prev].d.begin(),BS.nodes[prev].d.end());
    for(shi k = 0;!ds.empty();k++){
        for(shi d : ds){
            if(d-k < 0){
                vitr.push_back(d);
                continue;
            }
            if(BL[d-k] >= div - i - k - 1){
                vitr.push_back(d);
                continue;
            }
            BL[d-k] = div - i - k - 1;
        }
        for(shi d : vitr) ds.erase(d);
        vitr.clear();
    }

    pipi ans = max(make_pair(FL.back(),make_pair(shi(N - FL.back()),div)),make_pair(BL.back(),make_pair((shi)0,shi(div - BL.back()))));
    for(shi i = 0;i < N-1;i++) ans = max(ans, make_pair(shi(FL[i] + BL[N-2-i]),make_pair(shi(i - FL[i] + 1),shi(div - BL[N-2-i]))));
    if(is_rev) ans.second.second = T.size() - ans.second.second - ans.first;
    return ans;
}

bool is_possible(str S, str T, shi ss, shi st, shi sz){
    str S2(S.begin() + ss,S.begin() + ss + sz), T2(T.begin() + st,T.begin() + st + sz);
    for(shi i = 0;i < sz;i++){
        if(S2 == T2) return 1;
        rotate(T2.begin(),T2.begin()+1,T2.end());
    }
    reverse(T2.begin(),T2.end());
    for(shi i = 0;i < sz;i++){
        if(S2 == T2) return 1;
        rotate(T2.begin(),T2.begin()+1,T2.end());
    }
    return 0;
}

int main(){
    string S,T;
    cin >> S >> T;

    Trie FS,BS;
    for(shi s = 0;s < S.size();s++){
        FS.insert(S,s,S.size());
    }
    reverse(S.begin(),S.end());
    for(shi s = 0;s < S.size();s++){
        BS.insert(S,s,S.size());
    }
    
    pipi ans = {0,{0,0}};
    for(shi i = 0;i < T.size();i++){
        ans = max(ans,calc_w_div(T,i,FS,BS,S.size()));
    }
    reverse(T.begin(),T.end());
    for(shi i = 0;i < T.size();i++){
        ans = max(ans,calc_w_div(T,i,FS,BS,S.size(),1));
    }
    // reverse(T.begin(),T.end());
    // reverse(S.begin(),S.end());
    // if(!is_possible(S,T,ans.second.first,ans.second.second,ans.first)){
    //     cout << "hallo!!!\n" << S << '\n' << T << '\n';
    //     cout << '\n';
    // }
    cout << ans.first << '\n' << ans.second.first << ' ' << ans.second.second;
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40