Đăng nhập để hỏi chi tiết
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
TRẢ LỜI
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define int long long
#define fast ios::sync_with_stdio(false); cin.tie(nullptr)
struct Fenwick {
int n;
vector<int> b;
Fenwick() {}
Fenwick(int n) { init(n); }
void init(int n) {
this->n = n;
b.assign(n + 1, 0);
}
void add(int i, int v) {
for (++i; i <= n; i += i & -i) b[i] += v;
}
int sum(int i) {
if (i < 0) return 0;
int s = 0;
for (++i; i > 0; i -= i & -i) s += b[i];
return s;
}
int get(int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
};
struct Seg {
int n;
vector<int> *a;
vector<int> t;
int better(int i, int j) {
if ((*a)[i] != (*a)[j]) return ((*a)[i] < (*a)[j] ? i : j);
return min(i, j);
}
void build(int v, int l, int r) {
if (l == r) {
t[v] = l;
return;
}
int m = (l + r) >> 1;
build(v << 1, l, m);
build(v << 1 | 1, m + 1, r);
t[v] = better(t[v << 1], t[v << 1 | 1]);
}
void init(vector<int> &v) {
a = &v;
n = (int)v.size();
t.assign(4 * n, 0);
build(1, 0, n - 1);
}
int query(int v, int l, int r, int u, int w) {
if (u <= l && r <= w) return t[v];
int m = (l + r) >> 1;
if (w <= m) return query(v << 1, l, m, u, w);
if (u > m) return query(v << 1 | 1, m + 1, r, u, w);
int x = query(v << 1, l, m, u, w);
int y = query(v << 1 | 1, m + 1, r, u, w);
return better(x, y);
}
int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
void build_sa(const vector<int> &s, vector<int> &sa, vector<int> &rk) {
int n = (int)s.size();
int mx = *max_element(s.begin(), s.end()) + 1;
sa.resize(n);
rk.resize(n);
vector<int> x(n), y(n), c(max(n, mx) + 1);
for (int i = 0; i < n; i++) x[i] = s[i];
for (int i = 0; i < mx; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i]]++;
for (int i = 1; i < mx; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
int p = 0;
for (int k = 1; k < n; k <<= 1) {
p = 0;
for (int i = n - k; i < n; i++) y[p++] = i;
for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
fill(c.begin(), c.begin() + mx, 0);
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < mx; i++) c[i] += c[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
y[sa[0]] = 0;
p = 1;
for (int i = 1; i < n; i++) {
int a1 = x[sa[i]], b1 = (sa[i] + k < n ? x[sa[i] + k] : -1);
int a0 = x[sa[i - 1]], b0 = (sa[i - 1] + k < n ? x[sa[i - 1] + k] : -1);
if (a1 != a0 || b1 != b0) p++;
y[sa[i]] = p - 1;
}
x.swap(y);
mx = p;
if (p == n) break;
}
for (int i = 0; i < n; i++) rk[sa[i]] = i;
}
void build_lcp(const vector<int> &s, const vector<int> &sa, const vector<int> &rk, vector<int> &lcp) {
int n = (int)s.size();
lcp.assign(n, 0);
int h = 0;
for (int i = 0; i < n; i++) {
int r = rk[i];
if (r == 0) continue;
int j = sa[r - 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[r] = h;
if (h) h--;
}
}
struct Node {
int l, r, d, lc, rc, pos;
bool leaf;
};
signed main() {
fast;
int n, k;
cin >> n >> k;
vector<int> a, sid, len;
a.reserve(200000);
sid.reserve(200000);
len.reserve(200000);
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int m = (int)s.size();
for (int j = 0; j < m; j++) {
a.push_back(s[j] - 'a' + 1);
sid.push_back(i);
len.push_back(m - j);
}
a.push_back(27 + i);
sid.push_back(0);
len.push_back(0);
}
a.push_back(0);
sid.push_back(0);
len.push_back(0);
int m = (int)a.size();
vector<int> sa, rk, lcp;
build_sa(a, sa, rk);
build_lcp(a, sa, rk, lcp);
Seg seg;
seg.init(lcp);
vector<Node> tr;
tr.reserve(2 * m);
vector<array<int, 4>> st;
st.push_back({0, m - 1, -1, -1});
while (!st.empty()) {
auto [l, r, p, sd] = st.back();
st.pop_back();
int id = (int)tr.size();
tr.push_back({l, r, 0, -1, -1, -1, l == r});
if (p != -1) {
if (sd == 0) tr[p].lc = id;
else tr[p].rc = id;
}
if (l == r) {
tr[id].d = len[sa[l]];
tr[id].pos = sa[l];
continue;
}
int q = seg.query(l + 1, r);
tr[id].d = lcp[q];
st.push_back({q, r, id, 1});
st.push_back({l, q - 1, id, 0});
}
vector<int> ord((int)tr.size());
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
if (tr[x].r != tr[y].r) return tr[x].r < tr[y].r;
return x < y;
});
Fenwick fw(m);
vector<int> last(n + 1, -1);
vector<char> good(tr.size(), 0);
int ptr = 0;
for (int i = 0; i < m; i++) {
int c = sid[sa[i]];
if (c) {
if (last[c] != -1) fw.add(last[c], -1);
fw.add(i, 1);
last[c] = i;
}
while (ptr < (int)ord.size() && tr[ord[ptr]].r == i) {
int id = ord[ptr];
int cnt = fw.get(tr[id].l, tr[id].r);
if (cnt >= k) good[id] = 1;
ptr++;
}
}
vector<int> ans(n + 1, 0);
vector<pair<int, int>> q;
q.push_back({0, 0});
while (!q.empty()) {
auto [u, cur] = q.back();
q.pop_back();
if (good[u]) cur = max(cur, tr[u].d);
if (tr[u].leaf) {
int c = sid[tr[u].pos];
if (c) ans[c] += cur;
} else {
if (tr[u].rc != -1) q.push_back({tr[u].rc, cur});
if (tr[u].lc != -1) q.push_back({tr[u].lc, cur});
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << (i == n ? '\n' : ' ');
}
return 0;
}uh
Hãy giúp mọi người biết câu trả lời này thế nào?
11 vote
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> buildSA(const string& s) {
int n = s.size();
vector<int> sa(n), r(n), tmp(n);
iota(sa.begin(), sa.end(), 0);
for (int i = 0; i < n; i++) r[i] = s[i];
for (int k = 1; k < n; k <<= 1) {
auto cmp = [&](int a, int b) {
if (r[a] != r[b]) return r[a] < r[b];
int ra = a+k < n ? r[a+k] : -1;
int rb = b+k < n ? r[b+k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
r = tmp;
if (r[sa[n-1]] == n-1) break;
}
return sa;
}
vector<int> buildLCP(const string& s, const vector<int>& sa) {
int n = s.size();
vector<int> rank_(n), lcp(n, 0);
for (int i = 0; i < n; i++) rank_[sa[i]] = i;
for (int i = 0, h = 0; i < n; i++) {
if (rank_[i] > 0) {
int j = sa[rank_[i]-1];
while (i+h < n && j+h < n && s[i+h] == s[j+h]) h++;
lcp[rank_[i]] = h;
if (h) h--;
}
}
return lcp;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<string> a(n);
for (auto& s : a) cin >> s;
// Ghép xâu với ký tự phân tách '\1' < 'a'
string concat;
vector<int> sid, pid;
for (int i = 0; i < n; i++) {
for (int j = 0; j < (int)a[i].size(); j++) {
sid.push_back(i); pid.push_back(j);
concat += a[i][j];
}
sid.push_back(-1); pid.push_back(-1);
concat += '\1';
}
int N = concat.size();
auto sa = buildSA(concat);
auto lcp = buildLCP(concat, sa);
// Union-Find
vector<int> par(N);
iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) -> int {
return par[x] == x ? x : par[x] = find(par[x]);
};
vector<vector<int>> cpos(N); // SA-index theo từng thành phần
vector<set<int>> cstr(N); // tập xâu phân biệt
vector<bool> csat(N, false);
vector<int> f(N, 0); // f[i] = độ dài tối đa hợp lệ của suffix tại SA[i]
for (int i = 0; i < N; i++) {
if (sid[sa[i]] >= 0) {
cpos[i].push_back(i);
cstr[i].insert(sid[sa[i]]);
if (k == 1) {
csat[i] = true;
f[i] = (int)a[sid[sa[i]]].size() - pid[sa[i]];
}
}
}
// Sắp xếp cạnh theo LCP giảm dần (cạnh e nối SA[e] và SA[e+1], trọng số = lcp[e+1])
vector<int> edges(N-1);
iota(edges.begin(), edges.end(), 0);
sort(edges.begin(), edges.end(), [&](int a, int b) {
return lcp[a+1] > lcp[b+1];
});
for (int e : edges) {
int u = find(e), v = find(e+1);
if (u == v) continue;
int lv = lcp[e+1];
if (lv == 0) break;
// Small-to-large: u là thành phần lớn hơn
if (cpos[u].size() < cpos[v].size()) swap(u, v);
bool usat = csat[u], vsat = csat[v];
for (int s : cstr[v]) cstr[u].insert(s);
cstr[v].clear();
bool now_sat = (int)cstr[u].size() >= k;
csat[u] = now_sat;
if (now_sat) {
if (!usat)
for (int p : cpos[u]) if (!f[p]) f[p] = lv;
if (!vsat)
for (int p : cpos[v]) if (!f[p]) f[p] = lv;
}
for (int p : cpos[v]) cpos[u].push_back(p);
cpos[v].clear();
par[v] = u;
}
// Tổng hợp đáp án
vector<ll> ans(n, 0);
for (int i = 0; i < N; i++)
if (sid[sa[i]] >= 0)
ans[sid[sa[i]]] += f[i];
for (int i = 0; i < n; i++)
cout << ans[i] << " \n"[i==n-1];
return 0;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bạn muốn hỏi điều gì?
Đặt câu hỏiGroup 2K9 Ôn Thi ĐGNL & ĐGTD Miễn Phí
Anh ấy có một mảng a gồm n xấu, chỉ gồm các kí tự Latinh in thường. Với mỗi xâu a, bạn cần đếm xem có bao nhiêu cặp I, r mà xâu con
từ 1 tới r của a; là xâu con liên tiếp của ít nhất k xấu trong mảng a.
Input
• Dòng đầu chửa hai số nguyên dương n, k. (1≤n, k <10).
• dòng tiếp theo, mỗi ...
Bảng tin
Bạn muốn hỏi điều gì?
Đặt câu hỏi
Cơ quan chủ quản: Công ty Cổ phần Công nghệ Giáo dục Thành Phát
Tải ứng dụng
Inbox: m.me/hoidap247online
Trụ sở: Tầng 7, Tòa Intracom, số 82 Dịch Vọng Hậu, Cầu Giấy, Hà Nội.
Giấy phép thiết lập mạng xã hội trên mạng số 331/GP-BTTTT do Bộ Thông tin và Truyền thông.
1396
915
1041
ae bình tĩnh
217
3596
122
Woah nếu không dùng AI thế thì bạn tự giải bằng thực lực trình ít nhất phải tst rồi bạn `->` có thể khẳng định là mù được không? t còn chả phải thằng trả lời câu này? ngooo thì bớt phát biểu
0
100
0
có thể khẳng định là mù được không? t còn chả phải thằng trả lời câu này? ngooo thì bớt phát biểu Mình nói bạn hồi nào
217
3596
122
nếu thế thì có biết sarcasm là gì ko? ko biết tự lên mạng tra nhé "t thề là ko phải AI đâu 😂" = "AI là quá rõ"
217
3596
122
m miền nam hay trung đấy
0
100
0
"t thề là ko phải AI đâu 😂" = "AI là quá rõ" Oke cái này mình không hiểu lỗi mình
0
100
0
m miền nam hay trung đấy Có cần thiết trả lời không?
0
100
0
mà bạn llm cũng khác gì tụi nó mà chửi người ta :)