Hướng dẫn giải của [CSES 2107] String Functions
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.
Đầu tiên ta tính các giá trị ~z~ bằng giải thuật Z. Sau đó, ta tính các giá trị ~\pi~ từ các giá trị ~z~.
Nhận xét 1: Nếu ~z(i)>0~, thì ~\pi(i+z(i)-1) \ge z(i)~, bởi vì một tiền tố có độ dài ~z(i)~ kết thúc tại vị trí ~i+z(i)-1~.
Nhận xét 2: ~\pi(i) \ge \pi(i+1)-1~, bởi vì nếu một tiền tố có độ dài ~\pi(i+1)~ kết thúc tại vị trí ~i+1~, thì cũng có một tiền tố có độ dài ~\pi(i+1)-1~ kết thúc tại vị trí ~i~.
Đoạn mã sau tính các giá trị ~\pi~ trong hai pha. Đầu tiên ta tính các giá trị "đỉnh" của ~\pi~ sử dụng Nhận xét 1, và sau đó tính các giá trị còn lại sử dụng Nhận xét 2. Chú ý rằng chỉ số bắt đầu từ 0 được sử dụng trong mã.
Đoạn mã chạy trong thời gian ~O(n)~, vì giải thuật Z chạy trong ~O(n)~ và các giá trị ~\pi~ được tính bằng hai vòng lặp tuyến tính.
#include <iostream>
#include <vector>
using namespace std;
vector<int> z_algo(string s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
z[i] = max(0, min(z[i - l], r - i));
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
int main() {
string s;
cin >> s;
int n = s.size();
vector<int> z = z_algo(s);
vector<int> p(n);
for (int i = n - 1; i > 0; i--) {
p[i + z[i] - 1] = z[i];
}
for (int i = n - 2; i > 0; i--) {
p[i] = max(p[i], p[i + 1] - 1);
}
for (auto x : z) {
cout << x << " ";
}
cout << "\n";
for (auto x : p) {
cout << x << " ";
}
cout << "\n";
}
Chương trình tham khảo
#include <iostream>
#include <vector>
using namespace std;
vector<int> z_algo(string s) {
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
z[i] = max(0, min(z[i - l], r - i));
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vector<int> z = z_algo(s);
vector<int> p(n);
for (int i = n - 1; i > 0; i--) {
p[i + z[i] - 1] = z[i];
}
for (int i = n - 2; i > 0; i--) {
p[i] = max(p[i], p[i + 1] - 1);
}
for (auto x : z) {
cout << x << " ";
}
cout << "\n";
for (auto x : p) {
cout << x << " ";
}
cout << "\n";
}
Bình luận