Hướng dẫn giải của [200 đề thầy Đức] Bài 124: Chuỗi con
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Cần tìm mọi vị trí bắt đầu ~i~ trên vòng tròn ~X~ sao cho ~Y~ xuất hiện. Vì ~X~ là vòng tròn nên ký tự thứ ~j~ của ~Y~ nằm ở vị trí ~(i + j) \bmod N~ của ~X~. Đánh số vị trí từ 1 và in tăng dần.
Sub 1: Xoay chuỗi rồi so sánh tiền tố — ~O(N \cdot N)~
Với mỗi ~i~, tạo chuỗi ~X~ xoay bắt đầu từ vị trí ~i~, rồi so sánh tiền tố với ~Y~. Đạt 20/20 test (~N~ nhỏ nên chạy kịp).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string x, y;
cin >> x >> y;
int n = x.size();
// Vét cạn: với mỗi vị trí bắt đầu i, tạo chuỗi xoay bắt đầu từ i rồi so sánh tiền tố với Y
bool printed = false;
for (int i = 0; i < n; i++) {
string rot = x.substr(i) + x.substr(0, i);
if (rot.compare(0, y.size(), y) == 0) {
if (printed) cout << " ";
cout << i + 1;
printed = true;
}
}
cout << "\n";
return 0;
}
Sub 2: So sánh theo chỉ số vòng tròn — ~O(N \cdot M)~
Không tạo chuỗi mới: ký tự thứ ~j~ của ~Y~ so với ~X[(i + j) \bmod N]~, dừng ngay khi lệch. Dùng phép chia lấy dư nên Y có thể vượt qua điểm nối vòng tròn. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string x, y;
cin >> x >> y;
int n = x.size(), m = y.size();
// Thử mọi vị trí bắt đầu i trên vòng tròn. Ký tự thứ j của Y nằm ở vị trí (i + j) % n của X.
// Dùng % để xử lý trường hợp Y vượt qua điểm nối vòng tròn.
bool printed = false;
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < m && ok; j++) {
if (x[(i + j) % n] != y[j]) ok = false;
}
if (ok) {
if (printed) cout << " ";
cout << i + 1; // đánh số vị trí từ 1
printed = true;
}
}
cout << "\n";
return 0;
}
Bình luận