VOJ - TWOOPERS
Source: TWOOPERS
Tags: String
Problem:
Cho hai xâu S và T. Thực hiện 2 thao tác trên xâu S:
- Chọn một vị trí bất kỳ trên S và xoay xâu sao cho vị trí đó trở thành vị trí bắt đầu.
- Chọn một vị trí bất kỳ trên S và thay thế chữ cái tại vị trí đó bằng một chữ cái bất kỳ.
Sau khi thực hiện 2 thao tác trên, kết quả thu được là xâu T. Đếm số cách thực hiện.
|S|, |T| ≤ 1e5. Xâu S và T chỉ gồm các chữ cái in hoa.
Ví dụ:
Input:
AHYANGYI YANGYIAH
Output:
8
Explanation:
Chọn vị trí thứ 3 trong xâu S (AHYANGYI) để xoay, sau đó tại mỗi vị trí đều có thể thay thế chữ cái tại đó bằng một chữ cái y hệt (A thay bằng A...)
Input:
VSUMSU MSUMSU
Output:
2
Explanation:
Cần thay thế chữ cái đầu tiên V thành M, sau đó có 2 cách xoay.
Solution:
Vì xâu S xoay vòng nên sẽ rất khó xử lý, do đó ta cần nhân đôi xâu S lên. Sau khi nhân đôi xâu S lên, bài toán trở thành "Tìm số vị trí trong S mà xâu con có N chữ số (N là độ dài xâu T) sai khác với xâu T tại không quá 1 vị trí".
Để giải quyết bài toán này ý tưởng của ta là tìm một vị trí sai khác giữa xâu con đang xét và T, sau đó kiểm tra 2 phần còn lại còn giống nhau không. Từ đây ta có 2 cách làm:
Cách 1: Sử dụng Hash + Binary Search:
Ta tìm vị trí đầu tiên sai khác với T bằng Binary Search, gọi i là vị trí bắt đầu của xâu con đang xét, gọi j là vị trí đang kiểm tra, nếu hash đoạn i → j của xâu S bằng với hash đoạn từ đầu đến chữ cái thứ j - i + 1 trong xâu T thì nghiễm nhiên đoạn đằng trước sẽ giống nhau và ta tiếp tục tìm ở đoạn sau, nếu không thì tìm ở đoạn trước và cứ thế...
Độ phức tạp O(NlogN)
Code:
#include <iostream>
using namespace std;
string s, t; int n;
const long long MOD = 1e9 + 7;
long long pow26[100001], hashS[200000], hashT[100000], res;
long long getHashS(int i, int j) {
if (i > j) return 0;
if (i == 0) return hashS[j];
return (hashS[j] - hashS[i - 1] * pow26[j - i + 1] + MOD * MOD) % MOD;
}
long long getHashT(int i, int j) {
if (i > j) return 0;
if (i == 0) return hashT[j];
return (hashT[j] - hashT[i - 1] * pow26[j - i + 1] + MOD * MOD) % MOD;
}
int main() {
cin >> s >> t;
if (s.length() != t.length()) {
cout << 0; return 0;
}
n = s.length();
pow26[0] = 1;
for (int i = 1; i <= n; i++)
pow26[i] = pow26[i - 1] * 26 % MOD;
s = s + s;
hashS[0] = s[0] - 65;
for (int i = 1; i < 2 * n; i++)
hashS[i] = (hashS[i - 1] * 26 + s[i] - 65) % MOD;
hashT[0] = t[0] - 65;
for (int i = 1; i < n; i++)
hashT[i] = (hashT[i - 1] * 26 + t[i] - 65) % MOD;
for (int i = 0; i < n; i++) {
int x = i - 1;
for (int l = i, r = i + n - 1, m; l <= r;) {
m = (l + r) / 2;
if (getHashS(i, m) == hashT[m - i])
x = m, l = m + 1;
else r = m - 1;
}
if (x == i + n - 1) res += n;
else if (getHashS(x + 2, i + n - 1) == getHashT(x - i + 2, n - 1))
++res;
}
cout << res;
}
Cách 2: Sử dụng Z function:
Bản thân mình là một người khá "dị ứng" với Hash, bởi vì cảm giác không chắc chắn. Nên mình luôn thích sử dụng hàm Z hoặc KMP hơn.
Gọi pre[i] là độ dài đoạn tiền tố dài nhất của xâu T trùng với đoạn con của S bắt đầu từ i, pre[i] được tính dễ dàng bằng hàm Z. Sau đó ta đi ngược xâu T và S lại, tạo mảng suf, gọi suf[i] là độ dài đoạn hậu tố dài nhất của xâu T trùng với đoạn con của S kết thúc tại i. Tại đây chỉ cần kiểm tra, nếu pre[i] = N thì nguyên đoạn con bắt đầu từ i đã trùng với T, nếu không thì pre[i] + suf[i + N - 1] = N - 1 thì đoạn con đó sai khác với T đúng một chỗ.
Độ phức tạp O(2 * N)
Code: (tự bản thân mình cũng thấy code hàm Z trong bài này tương đối dài và rắc rối vì phải đi ngược xâu nữa, nên mình khuyên nếu đã hiểu rồi thì nên tự code lại thay vì đi coi code mình để hiểu)
#include <iostream>
using namespace std;
string s, t;
int n, z[100000], pre[200000], suf[200000];
long long res;
int main() {
cin >> s >> t;
if (s.length() != t.length()) {
cout << 0; return 0;
}
n = s.length();
s = s + s;
z[0] = n;
for (int l = 0, r = 0, i = 1; i < n; i++)
if (i > r) {
l = r = i;
for (; r < n && t[r] == t[r - l]; r++);
z[i] = r - l; --r;
}
else if (z[i - l] < r - i + 1)
z[i] = z[i - l];
else {
l = i;
for (; r < n && t[r] == t[r - l]; r++);
z[i] = r - l; --r;
}
for (int l = -1, r = -1, i = 0; i < 2 * n; i++)
if (i > r) {
l = r = i;
for (; r < 2 * n && r - l + 1 <= n && s[r] == t[r - l]; r++);
pre[i] = r - l; --r;
}
else if (z[i - l] < r - i + 1)
pre[i] = z[i - l];
else {
l = i;
for (; r < 2 * n && r - l + 1 <= n && s[r] == t[r - l]; r++);
pre[i] = r - l; --r;
}
z[n - 1] = n;
for (int l = n - 1, r = n - 1, i = n - 2; i >= 0; i--)
if (i < l) {
l = r = i;
for (; l >= 0 && t[l] == t[n - r + l - 1]; l--);
z[i] = r - l; ++l;
}
else if (z[n - r + i - 1] < i - l + 1)
z[i] = z[n - r + i - 1];
else {
r = i;
for (; l >= 0 && t[l] == t[n - r + l - 1]; l--);
z[i] = r - l; ++l;
}
for (int l = 2 * n, r = 2 * n, i = 2 * n - 1; i >= 0; i--)
if (i < l) {
l = r = i;
for (; l >= 0 && r - l + 1 <= n && s[l] == t[n - r + l - 1]; l--);
suf[i] = r - l; ++l;
}
else if (z[n - r + i - 1] < i - l + 1)
suf[i] = z[n - r + i - 1];
else {
r = i;
for (; l >= 0 && r - l + 1 <= n && s[l] == t[n - r + l - 1]; l--);
suf[i] = r - l; ++l;
}
for (int i = 0; i < n; i++)
if (pre[i] == n) res += n;
else if (pre[i] + suf[i + n - 1] == n - 1)
++res;
cout << res;
}
Tags: String
Problem:
Cho hai xâu S và T. Thực hiện 2 thao tác trên xâu S:
- Chọn một vị trí bất kỳ trên S và xoay xâu sao cho vị trí đó trở thành vị trí bắt đầu.
- Chọn một vị trí bất kỳ trên S và thay thế chữ cái tại vị trí đó bằng một chữ cái bất kỳ.
Sau khi thực hiện 2 thao tác trên, kết quả thu được là xâu T. Đếm số cách thực hiện.
|S|, |T| ≤ 1e5. Xâu S và T chỉ gồm các chữ cái in hoa.
Ví dụ:
Input:
AHYANGYI YANGYIAH
Output:
8
Explanation:
Chọn vị trí thứ 3 trong xâu S (AHYANGYI) để xoay, sau đó tại mỗi vị trí đều có thể thay thế chữ cái tại đó bằng một chữ cái y hệt (A thay bằng A...)
Input:
VSUMSU MSUMSU
Output:
2
Explanation:
Cần thay thế chữ cái đầu tiên V thành M, sau đó có 2 cách xoay.
Solution:
Vì xâu S xoay vòng nên sẽ rất khó xử lý, do đó ta cần nhân đôi xâu S lên. Sau khi nhân đôi xâu S lên, bài toán trở thành "Tìm số vị trí trong S mà xâu con có N chữ số (N là độ dài xâu T) sai khác với xâu T tại không quá 1 vị trí".
Để giải quyết bài toán này ý tưởng của ta là tìm một vị trí sai khác giữa xâu con đang xét và T, sau đó kiểm tra 2 phần còn lại còn giống nhau không. Từ đây ta có 2 cách làm:
Cách 1: Sử dụng Hash + Binary Search:
Ta tìm vị trí đầu tiên sai khác với T bằng Binary Search, gọi i là vị trí bắt đầu của xâu con đang xét, gọi j là vị trí đang kiểm tra, nếu hash đoạn i → j của xâu S bằng với hash đoạn từ đầu đến chữ cái thứ j - i + 1 trong xâu T thì nghiễm nhiên đoạn đằng trước sẽ giống nhau và ta tiếp tục tìm ở đoạn sau, nếu không thì tìm ở đoạn trước và cứ thế...
Độ phức tạp O(NlogN)
Code:
#include <iostream>
using namespace std;
string s, t; int n;
const long long MOD = 1e9 + 7;
long long pow26[100001], hashS[200000], hashT[100000], res;
long long getHashS(int i, int j) {
if (i > j) return 0;
if (i == 0) return hashS[j];
return (hashS[j] - hashS[i - 1] * pow26[j - i + 1] + MOD * MOD) % MOD;
}
long long getHashT(int i, int j) {
if (i > j) return 0;
if (i == 0) return hashT[j];
return (hashT[j] - hashT[i - 1] * pow26[j - i + 1] + MOD * MOD) % MOD;
}
int main() {
cin >> s >> t;
if (s.length() != t.length()) {
cout << 0; return 0;
}
n = s.length();
pow26[0] = 1;
for (int i = 1; i <= n; i++)
pow26[i] = pow26[i - 1] * 26 % MOD;
s = s + s;
hashS[0] = s[0] - 65;
for (int i = 1; i < 2 * n; i++)
hashS[i] = (hashS[i - 1] * 26 + s[i] - 65) % MOD;
hashT[0] = t[0] - 65;
for (int i = 1; i < n; i++)
hashT[i] = (hashT[i - 1] * 26 + t[i] - 65) % MOD;
for (int i = 0; i < n; i++) {
int x = i - 1;
for (int l = i, r = i + n - 1, m; l <= r;) {
m = (l + r) / 2;
if (getHashS(i, m) == hashT[m - i])
x = m, l = m + 1;
else r = m - 1;
}
if (x == i + n - 1) res += n;
else if (getHashS(x + 2, i + n - 1) == getHashT(x - i + 2, n - 1))
++res;
}
cout << res;
}
Cách 2: Sử dụng Z function:
Bản thân mình là một người khá "dị ứng" với Hash, bởi vì cảm giác không chắc chắn. Nên mình luôn thích sử dụng hàm Z hoặc KMP hơn.
Gọi pre[i] là độ dài đoạn tiền tố dài nhất của xâu T trùng với đoạn con của S bắt đầu từ i, pre[i] được tính dễ dàng bằng hàm Z. Sau đó ta đi ngược xâu T và S lại, tạo mảng suf, gọi suf[i] là độ dài đoạn hậu tố dài nhất của xâu T trùng với đoạn con của S kết thúc tại i. Tại đây chỉ cần kiểm tra, nếu pre[i] = N thì nguyên đoạn con bắt đầu từ i đã trùng với T, nếu không thì pre[i] + suf[i + N - 1] = N - 1 thì đoạn con đó sai khác với T đúng một chỗ.
Độ phức tạp O(2 * N)
Code: (tự bản thân mình cũng thấy code hàm Z trong bài này tương đối dài và rắc rối vì phải đi ngược xâu nữa, nên mình khuyên nếu đã hiểu rồi thì nên tự code lại thay vì đi coi code mình để hiểu)
#include <iostream>
using namespace std;
string s, t;
int n, z[100000], pre[200000], suf[200000];
long long res;
int main() {
cin >> s >> t;
if (s.length() != t.length()) {
cout << 0; return 0;
}
n = s.length();
s = s + s;
z[0] = n;
for (int l = 0, r = 0, i = 1; i < n; i++)
if (i > r) {
l = r = i;
for (; r < n && t[r] == t[r - l]; r++);
z[i] = r - l; --r;
}
else if (z[i - l] < r - i + 1)
z[i] = z[i - l];
else {
l = i;
for (; r < n && t[r] == t[r - l]; r++);
z[i] = r - l; --r;
}
for (int l = -1, r = -1, i = 0; i < 2 * n; i++)
if (i > r) {
l = r = i;
for (; r < 2 * n && r - l + 1 <= n && s[r] == t[r - l]; r++);
pre[i] = r - l; --r;
}
else if (z[i - l] < r - i + 1)
pre[i] = z[i - l];
else {
l = i;
for (; r < 2 * n && r - l + 1 <= n && s[r] == t[r - l]; r++);
pre[i] = r - l; --r;
}
z[n - 1] = n;
for (int l = n - 1, r = n - 1, i = n - 2; i >= 0; i--)
if (i < l) {
l = r = i;
for (; l >= 0 && t[l] == t[n - r + l - 1]; l--);
z[i] = r - l; ++l;
}
else if (z[n - r + i - 1] < i - l + 1)
z[i] = z[n - r + i - 1];
else {
r = i;
for (; l >= 0 && t[l] == t[n - r + l - 1]; l--);
z[i] = r - l; ++l;
}
for (int l = 2 * n, r = 2 * n, i = 2 * n - 1; i >= 0; i--)
if (i < l) {
l = r = i;
for (; l >= 0 && r - l + 1 <= n && s[l] == t[n - r + l - 1]; l--);
suf[i] = r - l; ++l;
}
else if (z[n - r + i - 1] < i - l + 1)
suf[i] = z[n - r + i - 1];
else {
r = i;
for (; l >= 0 && r - l + 1 <= n && s[l] == t[n - r + l - 1]; l--);
suf[i] = r - l; ++l;
}
for (int i = 0; i < n; i++)
if (pre[i] == n) res += n;
else if (pre[i] + suf[i + n - 1] == n - 1)
++res;
cout << res;
}
Nhận xét
Đăng nhận xét