제출 #1306583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306583		veham	Necklace (Subtask 1-3) (BOI19_necklace1)	C++20	0 / 85	214 ms	458424 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];
    // vi d;
    Node(int x){
        for(int i = 0;i < 26;i++) idxs[i] = -1;
    }
    Node(){}
};

struct Trie{
    Node nodes[1500*3001/2+3];
    int last = 0;
    Trie(){
        nodes[last++] = Node(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'] = last, nodes[last++] = Node(0);
            curr = nodes[curr].idxs[S[i]-'a'];
            // nodes[curr].d.push_back(i);
        }
    }
};

vi mat(str &needle, str &hay){
    str c = needle + '#' + hay;
    vi pi(c.size(),0);
    for(int i = 1;i < pi.size();i++){
        for(pi[i] = pi[i-1]+1;pi[i] != 0;pi[i] = pi[pi[i] - 2] + 1){
            if(c[i] == c[pi[i]-1]) break;
            if(pi[i] == 1){
                pi[i] = 0;
                break;
            }
        }
    }
    vi ans;
    for(int i = needle.size()+1;i < c.size();i++) if(pi[i] == needle.size()) ans.push_back(i - needle.size() - 1);
    return ans;
}

pipi calc_w_div(str &S, 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;
    }
    str needle(T.begin() + div, T.begin() + div + i);
    vi d = mat(needle,S);
    set<int> ds(d.begin(),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;
    }
    reverse(S.begin(),S.end());
    needle = str((str::reverse_iterator)(T.begin()+div-1),(str::reverse_iterator)(T.begin()+i));
    d = mat(needle,S);
    reverse(S.begin(),S.end());    
    ds = set<int>(d.begin(),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;
    BL.clear(),FL.clear(),needle.clear(),d.clear();
    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(S,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(S,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: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40