Hướng dẫn giải của [200 đề thầy Đức] Bài 121: Ước chuỗi
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 của chuỗi ~S~ là chuỗi ngắn nhất ~X~ sao cho ghép nhiều lần ~X~ ra đúng ~S~. Thực chất cần tìm chu kỳ nhỏ nhất của ~S~ thỏa mãn độ dài chu kỳ chia hết độ dài ~S~.
Sub 1: Vét cạn thử mọi độ dài p — ~O(n^2)~
Thử từng ~p~ là ước của độ dài ~n~, kiểm tra ~S[i] = S[i \bmod p]~ với mọi ~i~. Gặp ~p~ đầu tiên thỏa mãn thì in ~S[0..p-1]~. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
// Vét cạn: thử mọi độ dài p là ước của n, kiểm tra s có phải lặp lại chuỗi s[0..p-1] không
for (int p = 1; p <= n; p++) {
if (n % p != 0) continue;
bool ok = true;
for (int i = 0; i < n && ok; i++) {
if (s[i] != s[i % p]) ok = false;
}
if (ok) {
cout << s.substr(0, p) << "\n";
return 0;
}
}
return 0;
}
Sub 2: Hàm pi của KMP — ~O(n)~
Hàm pi cho biết độ dài tiền tố dài nhất vừa là tiền tố vừa là hậu tố. Chu kỳ nhỏ nhất là ~p = n - pi[n-1]~. Nếu ~p~ không chia hết ~n~ thì ~S~ không lặp lại được, ước chính là ~S~. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
// Hàm pi (prefix function) của KMP:
// pi[i] là độ dài tiền tố dài nhất vừa là tiền tố vừa là hậu tố của s[0..i].
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
// Chu kỳ nhỏ nhất p = n - pi[n-1]. Nếu p chia hết n thì ước là s[0..p-1], không thì là chính s
int p = n - pi[n - 1];
if (n % p != 0) p = n;
cout << s.substr(0, p) << "\n";
return 0;
}
Bình luận