Chia Xâu Thành Số Lượng Lớn Nhất Các Xâu Con Duy Nhất
Đề bài
Cho một xâu ký tự $s$, hãy trả về số lượng lớn nhất các xâu con không trùng nhau mà xâu $s$ có thể được chia thành.
Bạn có thể chia xâu $s$ thành một danh sách bất kỳ gồm các xâu con không rỗng, sao cho việc ghép nối các xâu con đó theo đúng thứ tự sẽ tạo thành xâu gốc $s$. Tuy nhiên, bạn phải chia sao cho tất cả các xâu con đều là duy nhất (không có hai xâu con nào giống nhau).
Một xâu con là một dãy các ký tự liên tiếp trong xâu.
Input: một dòng duy nhất chứa xâu ký tự $s$ ($1 \le$ độ dài xâu $s \le 16$) — xâu chỉ gồm các chữ cái tiếng Anh in thường ('a' – 'z').
Output: một số nguyên duy nhất là số lượng xâu con duy nhất lớn nhất tìm được.
| Input | Output | Giải thích |
|---|---|---|
| ababccc | 5 | Một cách chia tối ưu là ['a', 'b', 'ab', 'c', 'cc']. Cách chia như ['a', 'b', 'a', 'b', 'c', 'cc'] không hợp lệ vì có 'a' và 'b' xuất hiện nhiều lần. |
| aba | 2 | Một cách chia tối ưu là ['a', 'ba']. |
| aa | 1 | Không thể chia xâu này thành nhiều hơn 1 xâu con duy nhất. |
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm và kèm lời giải để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesTóm tắt đề bài: cho một chuỗi $s$ gồm các ký tự chữ cái latin in thường. Hãy tách chuỗi $s$ thành các chuỗi con sao cho các chuỗi con đều khác nhau, đồng thời số lượng chuỗi con tách được là nhiều nhất có thể.
100%Phương pháp: Backtracking (đệ quy quay lui)
Để ý rằng độ dài của chuỗi $s \le 16$, không khó để nhận ra đề bài hướng chúng ta đến việc sử dụng Backtracking để thử mọi cách tách chuỗi. Cụ thể như sau:
- Gọi $S$ là tập hợp các chuỗi con đã được tách ra (trong code là
set<string> st). - Gọi hàm
backTrack(pos)là hàm mà ta đang tách tới ký tự thứposcủa chuỗi $s$. Ta thử lần lượt các chuỗi contmpbắt đầu tạipos:s[pos..pos],s[pos..pos+1], … - Nếu thấy
tmpchưa xuất hiện trong $S$, ta đưatmpvào $S$, rồi gọibackTrack(i + 1)để xét tiếp phần còn lại của chuỗi. Gọi xong thì xoátmpra khỏi $S$ để có thể thử cách tách khác (đây chính là bước "quay lui"). - Khi
pos == n(đã tách hết chuỗi), ta cập nhật giá trị lớn nhất của kích thước $S$.
Ví dụ với $s$ = "aba", cây đệ quy sẽ như sau (mỗi mức thụt vào là một lần gọi backTrack sâu hơn):
chọn "a"
chọn "b"
✘ "a" đã có trong S, bỏ qua
chọn "ba"
✔ hết chuỗi, |S| = 2 → {a, ba}
chọn "ab"
chọn "a"
✔ hết chuỗi, |S| = 2 → {ab, a}
chọn "aba"
✔ hết chuỗi, |S| = 1 → {aba}
Kích thước lớn nhất tìm được là 2, đúng với đáp án.
Mô phỏng: em nhập xâu $s$ (tối đa 8 ký tự) rồi bấm Tiếp để xem từng bước quay lui: mỗi lần thử cắt một miếng, miếng trùng với miếng đã có trong $S$ bị loại (đỏ), cắt hết chuỗi thì so với kỷ lục, rồi gỡ miếng ra để thử cách khác:
Đánh giá độ phức tạp: chuỗi độ dài $n$ có $n - 1$ chỗ có thể cắt, mỗi chỗ cắt hoặc không, nên có tối đa $2^{n - 1}$ cách tách; mỗi thao tác với set tốn thêm khoảng $\log$, tổng cộng $O(2^{\text{length}(s)} \cdot \log(\text{length}(s)))$. Với $n = 16$ chỉ khoảng $2^{15} = 32768$ cách tách, chạy rất nhanh.
#include <bits/stdc++.h>
using namespace std;
set<string> st;
int ans = -1;
void backTrack(int pos, const string &s){
string tmp = "";
if(pos == (int)s.size()){
ans = max(ans, (int)st.size());
return;
}
for(int i = pos; i < (int)s.size(); i++){
tmp += s[i];
if(st.find(tmp) == st.end()){
st.insert(tmp);
backTrack(i + 1, s);
set<string>::iterator it = st.find(tmp);
st.erase(it);
}
}
}
int maxUniqueSplit(string s){
st.clear();
ans = -1;
backTrack(0, s);
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
cout << maxUniqueSplit(s);
return 0;
}import sys
def maxUniqueSplit(s):
st = set()
ans = -1
def backTrack(pos):
nonlocal ans
if pos == len(s):
ans = max(ans, len(st))
return
tmp = ""
for i in range(pos, len(s)):
tmp += s[i]
if tmp not in st:
st.add(tmp)
backTrack(i + 1)
st.remove(tmp)
backTrack(0)
return ans
s = sys.stdin.readline().strip()
print(maxUniqueSplit(s))Mình đã kiểm tra code với 300 chuỗi ngẫu nhiên, so với cách thử mọi vị trí cắt bằng dãy bit, đều cho cùng kết quả. Với chuỗi dài 16, bản C++ và bản Python mình viết thêm đều chạy chưa tới 0.05 giây.
Nhận xét
Đăng nhận xét