Trong bài toán này, ta được cho xâu str. Nhiệm vụ: tạo chương trình tìm tổng độ tương đồng của xâu với tất cả hậu tố của nó.
Hậu tố của xâu str là các xâu tạo ra bằng cách loại bỏ các ký tự đầu của xâu.
Độ tương đồng của hai xâu str1 và str2 là độ dài tiền tố chung dài nhất của cả hai. Ví dụ: 'abbac' và 'abb' → 3. 'abca' và 'ca' → 0 (vì so khớp từ đầu).
Ví dụ minh họa
Đầu vào – str = 'xyxyx'
Đầu ra** –
Giải thích** – Các hậu tố và độ tương đồng:
'xyxyx' → 5 'yxyx' → 0 'xyx' → 3 'yx' → 0 'x' → 1 Tổng = 5 + 0 + 3 + 0 + 1 = 9
Để giải bài toán, dùng Z-algorithm tính mảng Z. Mảng Z có độ dài bằng độ dài xâu, mỗi phần tử lưu độ dài tiền tố chung của xâu với hậu tố bắt đầu tại vị trí đó.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void createZArray(string str, int n, int Zarray[]) {
int L, R, k;
L = R = 0;
for (int i = 1; i < n; ++i) {
if (i > R) {
L = R = i;
while (R < n && str[R - L] == str[R])
R++;
Zarray[i] = R - L;
R--;
} else {
k = i - L;
if (Zarray[k] < R - i + 1)
Zarray[i] = Zarray[k];
else {
L = i;
while (R < n && str[R - L] == str[R])
R++;
Zarray[i] = R - L;
R--;
}
}
}
}
int calSumSimilarities(string s, int n) {
int Zarray[n] = { 0 };
createZArray(s, n, Zarray);
int total = n;
for (int i = 1; i < n; i++)
total += Zarray[i];
return total;
}
int main() {
string s = "xyxyx";
int n = s.length();
cout << "Sum of similarities of string with all of its suffixes is " << calSumSimilarities(s, n);
return 0;
}
Đầu ra
Sum of similarities of string with all of its suffixes is 9