Hướng dẫn giải của Số gánh
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ậpTác giả: , , ,
Hiểu bài toán
Cho một chuỗi số S. Tìm độ dài lớn nhất của một chuỗi con liên tiếp nằm ở đầu S và cũng là chuỗi con liên tiếp nằm ở cuối S. Nếu không tồn tại chuỗi con như vậy (ngoại trừ chuỗi rỗng), in ra -1.
Ví dụ: Với S = '123123', ta có:
- Chuỗi con '1' ở đầu và cuối.
- Chuỗi con '12' ở đầu và cuối.
- Chuỗi con '123' ở đầu và cuối. Đáp án là 3.
Với S = '123456', không có chuỗi con nào nằm ở cả đầu và cuối (trừ chuỗi rỗng), nên đáp án là -1.
Các cách tiếp cận
Cách Brute Force (Duyệt tất cả)
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
long long kq = 0;
// Duyệt độ dài i từ 1 đến n-1
for (int i = 1; i < s.size(); i++) {
// Lấy chuỗi con đầu tiên độ dài i
string prefix = s.substr(0, i);
// Lấy chuỗi con cuối cùng độ dài i
string suffix = s.substr(s.size() - i, i);
if (prefix == suffix) {
kq = i;
}
}
if (kq == 0) cout << -1;
else cout << kq;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Cách tiếp cận này sử dụng vòng lặp để kiểm tra tất cả các độ dài có thể của chuỗi con (từ 1 đến n-1). Với mỗi độ dài i, nó tạo hai chuỗi con: một bắt đầu từ đầu chuỗi và một kết thúc ở cuối chuỗi. Nếu chúng giống nhau, cập nhật kết quả.
- Ưu điểm: Dễ hiểu, dễ cài đặt.
- Nhược điểm: Tốn thời gian do việc tạo chuỗi con và so sánh trong mỗi bước lặp. Nếu chuỗi dài, độ phức tạp O(n^2) có thể quá chậm.
Cách Two Pointers (Hai con trỏ)
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
int kq = -1;
int l = 0, r = s.size() - 1;
string s1 = "", s2 = "";
// Duyệt từ ngoài vào trong
while (l <= r) {
s1 = s1 + s[l]; // Chuỗi từ trái sang
s2 = s[r] + s2; // Chuỗi từ phải sang
if (s1 == s2) {
kq = s1.length(); // Cập nhật độ dài nếu khớp
}
l++;
r--;
}
cout << kq;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n)
Cách tiếp cận này xây dựng chuỗi con từ ngoài vào trong. Hai con trỏ trỏ vào đầu và cuối chuỗi.
s1được xây dựng bằng cách thêm ký tự từ trái sang phải.s2được xây dựng bằng cách thêm ký tự từ phải sang trái.- Mỗi bước, ta kiểm tra
s1có bằngs2không. Nếu có, ta lưu độ dài làm kết quả.
Phương pháp này vẫn tốn O(n^2) trong trường hợp xấu nhất (do so sánh chuỗi và ghép chuỗi), nhưng logic khá trực quan.
Cách KMP Algorithm (Knuth-Morris-Pratt)
#include <bits/stdc++.h>
using namespace std;
// Hàm tính mảng mảng tiền tố (prefix function)
vector<int> computeLPS(string pattern) {
int m = pattern.length();
vector<int> lps(m);
int len = 0;
lps[0] = 0;
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
int main() {
string s;
cin >> s;
int n = s.length();
if (n < 2) {
cout << -1;
return 0;
}
// Bước 1: Tìm tiền tố dài nhất của S mà cũng là hậu tố của S
// Trick: Ghép S với ký tự đặc biệt rồi tìm LPS
// Nhưng với bài này, ta có thể dùng KMP search để tìm S trong S (bỏ qua ký tự đầu)
// Hoặc đơn giản hơn: dùng mảng LPS của chính chuỗi S.
// Nếu dùng LPS của S, `lps[n-1]` cho biết độ dài tiền tố dài nhất trùng với hậu tố.
// Tuy nhiên, để đảm bảo không lấy cả chuỗi (nếu đề bài yêu cầu con strict bên trong),
// ta cần kiểm tra kỹ.
// Ví dụ: S = 'aba', lps = [0, 0, 1]. Kết quả mong muốn là 1 (chuỗi 'a').
// Ví dụ: S = 'ababa', lps = [0, 0, 1, 2, 3].
// Chuẩn hóa lại logic:
// Ta cần tìm độ dài `k` lớn nhất sao cho:
// S[0...k-1] == S[n-k...n-1]
// Đồng thời `k < n` (không lấy toàn bộ chuỗi).
vector<int> lps = computeLPS(s);
int candidate = lps[n - 1];
if (candidate == 0) {
cout << -1;
} else {
// Trong trường hợp đặc biệt, `candidate` có thể bằng n (với chuỗi lặp)
// Ví dụ S = 'aaaa', lps = [0,1,2,3].
// Nhưng đề bài chỉ quan tâm đến tiền tố nằm ở đầu và cuối.
// Nếu `candidate` == n, ta cần lùi về `lps[candidate-1]` để tìm tiền tố nhỏ hơn.
while (candidate > 0 && candidate >= n) {
candidate = lps[candidate - 1];
}
if (candidate == 0) cout << -1;
else cout << candidate;
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tối ưu nhất利用了 KMP Algorithm.
Bài toán này thực chất là tìm độ dài tiền tố dài nhất của chuỗi S mà đồng thời là hậu tố của S (với độ dài nhỏ hơn n).
Xây dựng mảng LPS (Longest Prefix Suffix):
- Mảng
lps[i]lưu độ dài lớn nhất của tiền tố con củaS[0...i]mà cũng là hậu tố của nó. lps[n-1]chính là độ dài tiền tố dài nhất của toàn bộ chuỗi S trùng với hậu tố của S.
- Mảng
Xử lý kết quả:
- Nếu
lps[n-1] == 0, in -1. - Nếu
lps[n-1] > 0, in ra giá trị đó.
- Nếu
Lưu ý: Trong một số trường hợp (ví dụ chuỗi lặp lại nhiều lần như 'aaaa'), lps[n-1] có thể bằng n. Tuy nhiên, theo logic bài toán 'Số gánh', ta thường chỉ quan tâm đến phần con bên trong. Nhưng trong code mẫu, ta thấy logic khá cơ bản. KMP cho phép tìm ra kết quả trong thời gian tuyến tính, phù hợp với chuỗi có độ dài lớn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(n) | Brute Force (Duyệt tất cả) |
| 2 | O(n^2) | O(n) | Two Pointers (Hai con trỏ) |
| 3 | O(n) | O(n) | KMP Algorithm (Knuth-Morris-Pratt) |
Bài học kinh nghiệm
- Bài toán này về bản chất là tìm tiền tố dài nhất của chuỗi mà đồng thời là hậu tố của chuỗi đó (với độ dài nhỏ hơn độ dài chuỗi).
- Mảng LPS trong thuật toán KMP được sinh ra để giải quyết chính xác bài toán này.
- Các giải pháp Brute Force chạy chậm nhưng dễ hình dung và chấp nhận được với dữ liệu nhỏ.
Lỗi thường gặp
- Quên trường hợp chuỗi rỗng hoặc độ dài chuỗi quá ngắn (dưới 2 ký tự).
- Trả về độ dài bằng chính độ dài chuỗi đầu vào nếu không kiểm tra kỹ điều kiện 'con' (ví dụ chuỗi 'aaaa' có thể cho kết quả là 4 nếu không loại trừ).
- Sử dụng
substrtrong vòng lặp lồng nhau có thể gây tràn bộ nhớ hoặc quá thời gian chạy trên chuỗi dài.
Bình luận