제출 #1306570

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

necklace

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

struct Node{
    int idxs[26];
    int backlink = -1;
    int f;
    char c;
    vi d;
    Node(int f, char c) : f(f), c(c) {
        for(int 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, int s, int e){
        int curr = 0;
        for(int 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);
        }
    }

    int trans(int 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);
    }

    int backlink(int 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, int div, Trie &FS, Trie &BS, int N, bool is_rev = 0){
    vi FL(N,0),BL(N,0);
    int 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<int> ds(FS.nodes[prev].d.begin(),FS.nodes[prev].d.end());
    vector<int> vitr;
    for(int k = 0;!ds.empty();k++){
        for(int 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(int 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<int>(BS.nodes[prev].d.begin(),BS.nodes[prev].d.end());
    for(int k = 0;!ds.empty();k++){
        for(int 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(int d : vitr) ds.erase(d);
        vitr.clear();
    }

    pipi ans = max(make_pair(FL.back(),make_pair(N - FL.back(),div)),make_pair(BL.back(),make_pair(0,div - BL.back())));
    for(int i = 0;i < N-1;i++) ans = max(ans, make_pair(FL[i] + BL[N-2-i],make_pair(i - FL[i] + 1,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, int ss, int st, int sz){
    str S2(S.begin() + ss,S.begin() + ss + sz), T2(T.begin() + st,T.begin() + st + sz);
    for(int i = 0;i < sz;i++){
        if(S2 == T2) return 1;
        rotate(T2.begin(),T2.begin()+1,T2.end());
    }
    reverse(T2.begin(),T2.end());
    for(int 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(int s = 0;s < S.size();s++){
        FS.insert(S,s,S.size());
    }
    reverse(S.begin(),S.end());
    for(int s = 0;s < S.size();s++){
        BS.insert(S,s,S.size());
    }
    
    pipi ans = {0,{0,0}};
    for(int i = 0;i < T.size();i++){
        ans = max(ans,calc_w_div(T,i,FS,BS,S.size()));
    }
    reverse(T.begin(),T.end());
    for(int 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: 20 / 20
• Subtask 3: 0 / 40