Hướng dẫn giải của Đặt tên cho con
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for dctname: Đặt tên cho con
Hiểu bài toán
Cho hai xâu $s1$ và $s2$ (độ dài lên tới $10^6$). Nhiệm vụ tìm một xâu con chung (không nhất thiết liên tiếp) của $s1$ và $s2$ có thứ tự từ điển lớn nhất. Xâu $A$ có thứ tự từ điển lớn hơn xâu $B$ nếu:
- Tồn tại vị trí đầu tiên $i$ mà ký tự tại đó của $A$ lớn hơn ký tự tại đó của $B$.
- Hoặc nếu $B$ là tiền tố của $A$ thì $A$ lớn hơn $B$.
Ví dụ: 'g' > 'g' (không), 'g' > 'a' (có), nhưng theo ví dụ 'g' > 'g...' (vì độ dài).
Đề bài yêu cầu tìm xâu con chung có thứ tự từ điển lớn nhất.
Các cách tiếp cận
Cách Quy hoạch động với Truy vấn (Next Array)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1,s2;
if(!(getline(cin,s1))) return 0;
getline(cin,s2);
int n1=s1.size(), n2=s2.size();
// next1[i*26 + c] = vị trí xuất hiện của chữ c tại hoặc sau i, hoặc -1
vector<int> next1((n1+1)*26, -1), next2((n2+1)*26, -1);
for(int i=n1-1;i>=0;--i){
for(int c=0;c<26;++c) next1[i*26 + c] = next1[(i+1)*26 + c];
next1[i*26 + (s1[i]-'a')] = i;
}
for(int i=n2-1;i>=0;--i){
for(int c=0;c<26;++c) next2[i*26 + c] = next2[(i+1)*26 + c];
next2[i*26 + (s2[i]-'a')] = i;
}
string ans;
int p1=0, p2=0;
while(p1<=n1 && p2<=n2){
bool found=false;
for(int c=25;c>=0;--c){
int a = (p1<=n1 ? next1[p1*26 + c] : -1);
int b = (p2<=n2 ? next2[p2*26 + c] : -1);
if(a!=-1 && b!=-1){
ans.push_back('a'+c);
p1 = a + 1;
p2 = b + 1;
found=true;
break;
}
}
if(!found) break;
}
cout << ans;
}
- Time Complexity: O((N+M) * 26)
- Space Complexity: O((N+M) * 26)
Phương pháp này xây dựng bảng tra cứu next cho cả hai xâu. next[i][c] lưu vị trí xuất hiện đầu tiên của ký tự c tại hoặc sau chỉ số i. Việc xây dựng bảng mất O(N * 26). Sau đó, ta bắt đầu từ đầu hai xâu, tại mỗi bước, ta duyệt từ ký tự lớn nhất ('z') về nhỏ nhất ('a'). Ký tự nào xuất hiện ở cả hai xâu sau vị trí hiện tại được chọn. Nếu chọn ký tự c, ta cập nhật vị trí hiện tại lên next[p1][c] + 1 và next[p2][c] + 1. Quá trình này lặp lại cho đến khi không thể chọn thêm ký tự nào. Độ phức tạp truy vấn là O(26 * Length), tổng thể O((N+M) * 26).
Cách Sử dụng Danh sách vị trí và Binary Search
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
cin >> s1 >> s2;
vector<int> pos1[26], pos2[26];
for (int i = 0; i < (int)s1.size(); ++i) pos1[s1[i]-'a'].push_back(i);
for (int i = 0; i < (int)s2.size(); ++i) pos2[s2[i]-'a'].push_back(i);
string ans;
int p1 = -1, p2 = -1;
while (true) {
bool picked = false;
for (int c = 25; c >= 0; --c) {
if (pos1[c].empty() || pos2[c].empty()) continue;
auto it1 = upper_bound(pos1[c].begin(), pos1[c].end(), p1);
if (it1 == pos1[c].end()) continue;
auto it2 = upper_bound(pos2[c].begin(), pos2[c].end(), p2);
if (it2 == pos2[c].end()) continue;
ans.push_back(char('a' + c));
p1 = *it1;
p2 = *it2;
picked = true;
break;
}
if (!picked) break;
}
cout << ans << "\n";
}
- Time Complexity: O(N + M + L * log N)
- Space Complexity: O(N + M)
Thay vì lưu bảng tra cứu dày đặc, ta chỉ lưu các vị trí xuất hiện của từng ký tự trong các danh sách riêng biệt. Ở mỗi bước, ta duyệt từ 'z' về 'a', sử dụng upper_bound để tìm vị trí xuất hiện đầu tiên của ký tự đó lớn hơn vị trí hiện tại trong cả hai xâu. Nếu tìm thấy, ta chọn ký tự đó và cập nhật vị trí. Phương pháp này tiết kiệm bộ nhớ hơn và hiệu quả nếu các ký tự xuất hiện thưa thớt, nhưng trung bình vẫn có độ phức tạp logarit.
Cách Tham lam tối ưu với Duyệt Ký tự
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
cin >> s1 >> s2;
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> pos1(26), pos2(26);
for (int i = 0; i < n1; i++) pos1[s1[i] - 'a'].push_back(i);
for (int i = 0; i < n2; i++) pos2[s2[i] - 'a'].push_back(i);
string res;
int i = 0, j = 0;
while (true) {
bool found = false;
for (int c = 25; c >= 0; c--) {
auto it1 = lower_bound(pos1[c].begin(), pos1[c].end(), i);
auto it2 = lower_bound(pos2[c].begin(), pos2[c].end(), j);
if (it1 != pos1[c].end() && it2 != pos2[c].end()) {
res.push_back('a' + c);
i = *it1 + 1;
j = *it2 + 1;
found = true;
break;
}
}
if (!found) break;
}
cout << res << "\n";
}
- Time Complexity: O((N+M) log(N+M))
- Space Complexity: O(N+M)
Đây là phiên bản phổ biến của thuật toán tham lam. Ta xây dựng các danh sách vị trí cho từng ký tự. Trong mỗi bước lặp:
- Duyệt từ ký tự 'z' về 'a'.
- Kiểm tra xem ký tự đó có xuất hiện sau vị trí hiện tại trong cả
s1vàs2không bằng cách dùnglower_bound. - Nếu có, thêm ký tự đó vào kết quả, cập nhật vị trí hiện tại lên
vị_trí + 1và dừng bước. Vòng lặp kết thúc khi không còn ký tự nào thỏa mãn. Độ phức tạp là O(L * log N) với L là độ dài xâu kết quả.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O((N+M) * 26) | O((N+M) * 26) | Quy hoạch động với Truy vấn (Next Array) |
| 2 | O(N + M + L * log N) | O(N + M) | Sử dụng Danh sách vị trí và Binary Search |
| 3 | O((N+M) log(N+M)) | O(N+M) | Tham lam tối ưu với Duyệt Ký tự |
Bài học kinh nghiệm
- Bài toán có tính chất tham lam: Luôn chọn ký tự lớn nhất có thể ở bước hiện tại để đảm bảo thứ tự từ điển lớn nhất.
- Vấn đề trở thành bài toán tìm xâu con chung dài nhất (hoặc có thứ tự từ điển lớn nhất) có thể tạo bằng cách duyệt qua các vị trí.
- Việc sử dụng các cấu trúc dữ liệu hỗ trợ tìm kiếm nhanh (mảng
nexthoặc danh sách vị trí +binary search) là bắt buộc do giới hạn độ dài $10^6$.
Lỗi thường gặp
- Không xử lý đúng trường hợp một trong hai xâu đã hết ký tự để duyệt.
- Hiệu năng kém nếu sử dụng mảng 2 chiều full kích thước $10^6 \times 26$ (cần tối ưu bộ nhớ bằng mảng 1 chiều hoặc vector).
- Nhầm lẫn giữa
lower_boundvàupper_boundkhi tìm vị trí tiếp theo (cần vị trí >= hiện tại).
Bình luận