search

OnlyDeniko / CP_templates

Шаблоны по CP
0 stars 1 forks source link

Добавить суфмас за линию #22

Open OnlyDeniko opened 1 year ago

OnlyDeniko commented 1 year ago

` inline bool leq(int aq, int aw, int bq, int bw) { return (aq < bq || (aq == bq && aw <= bw)); }

inline bool leq(int aq, int aw, int ae, int bq, int bw, int be) { return (aq < bq || (aq == bq && leq(aw, ae, bw, be))); }

std::vector cc; static inline void radixPass(std::vector& aa, std::vector& bb, std::vector& rr, int NN, int KK) { cc.assign(KK + 1, 0); for (int i = 0; i < NN; ++i) { cc[rr[aa[i]]]++; } for (int i = 0, sum = 0; i <= KK; ++i) { int tt = cc[i]; cc[i] = sum; sum += tt; } for (int i = 0; i < NN; ++i) { bb[cc[rr[aa[i]]]++] = aa[i]; } }

void suffixArray(std::vector& TT, std::vector& SA, int NN, int KK) { int n_zero = (NN + 2) / 3, n_one = (NN + 1) / 3, n_two = NN / 3, n_o_two = n_zero + n_two; std::vector RR(n_o_two + 3); RR[n_o_two] = RR[n_o_two + 1] = RR[n_o_two + 2] = 0; std::vector SAS(n_o_two + 3); SAS[n_o_two] = SAS[n_o_two + 1] = SAS[n_o_two + 2] = 0; std::vector R_zero(n_zero), SA_zero(n_zero); for (int i = 0, j = 0; i < NN + (n_zero - n_one); ++i) { if (i % 3) { RR[j++] = i; } } std::vector T_two(TT.begin() + 2, TT.end()); std::vector T_one(TT.begin() + 1, TT.end()); radixPass(RR, SAS, T_two, n_o_two, KK); radixPass(SAS, RR, T_one, n_o_two, KK); radixPass(RR, SAS, TT, n_o_two, KK); int name = 0, cq = -1, cw = -1, ce = -1; for (int ii = 0; ii < n_o_two; ++ii) { if (TT[SAS[ii]] != cq || TT[SAS[ii] + 1] != cw || TT[SAS[ii] + 2] != ce) { name++; cq = TT[SAS[ii]]; cw = TT[SAS[ii] + 1]; ce = TT[SAS[ii] + 2]; } if (SAS[ii] % 3 == 1) { RR[SAS[ii] / 3] = name; } else { RR[SAS[ii] / 3 + n_zero] = name; } } if (name < n_o_two) { suffixArray(RR, SAS, n_o_two, name); for (int i = 0; i < n_o_two; ++i) { RR[SAS[i]] = i + 1; } } else { for (int i = 0; i < n_o_two; ++i) { SAS[RR[i] - 1] = i; } } for (int i = 0, j = 0; i < n_o_two; ++i) { if (SAS[i] < n_zero) { R_zero[j++] = 3 SAS[i]; } } radixPass(R_zero, SA_zero, TT, n_zero, KK); for (int pp = 0, t = n_zero - n_one, kk = 0; kk < NN; ++kk) { int ii = SAS[t] < n_zero ? SAS[t] 3 + 1 : (SAS[t] - n_zero) 3 + 2; int jj = SA_zero[pp]; if (SAS[t] < n_zero ? leq(TT[ii], RR[SAS[t] + n_zero], TT[jj], RR[jj / 3]) : leq(TT[ii], TT[ii + 1], RR[SAS[t] - n_zero + 1], TT[jj], TT[jj + 1], RR[jj / 3 + n_zero])) { SA[kk] = ii; ++t; if (t == n_o_two) { for (kk++; pp < n_zero; ++pp, ++kk) { SA[kk] = SA_zero[pp]; } } } else { SA[kk] = jj; pp++; if (pp == n_zero) { for (kk++; t < n_o_two; ++t, ++kk) { SA[kk] = SAS[t] < n_zero ? SAS[t] 3 + 1 : (SAS[t] - n_zero) * 3 + 2; } } } } }

void build_lcp(std::vector& TT, std::vector& sa, std::vector& lcp, int NN) { std::vector arr(NN); for (int i = 0; i < NN; ++i) { arr[sa[i]] = i; } lcp.resize(NN);

auto calc = [&](int indexl, int indexr, int pos) -> int {
    if (indexr == NN)
        return 0;
    int ans = pos;
    indexl = sa[indexl] + pos;
    indexr = sa[indexr] + pos;
    while (std::max(indexl, indexr) < NN) {
        if (TT[indexl] != TT[indexr])
            break;
        ++ans;
        ++indexl;
        ++indexr;
    }
    return ans;
};

lcp[arr[0]] = calc(arr[0], arr[0] + 1, 0);
for (int i = 1; i < NN; ++i) {
    lcp[arr[i]] = calc(arr[i], arr[i] + 1, std::max(0, lcp[arr[i - 1]] - 1));
}

}

void build(std::string& str, std::vector& sa, std::vector& lcp, int KK) { std::vector TT; TT.reserve(str.size()); for (auto& i : str) { if (i >= 'a') { TT.push_back(i - 'a'); } else { TT.push_back(static_cast(i + 26)); } } TT.push_back(0); TT.push_back(0); TT.push_back(0); sa.assign(str.size(), 0); // double tt = clock(); suffixArray(TT, sa, str.size(), KK); // tt = (clock() - tt) / CLOCKS_PER_SEC; // cout << "BUILD SA = " << tt << std::endl; // tt = clock(); build_lcp(TT, sa, lcp, str.size()); // tt = (clock() - tt) / CLOCKS_PER_SEC; // cout << "BUILD LCP = " << tt << std::endl; } `