let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Thuật toán Z

Thuật toán Z

Contents

Bài dịch từ Codeforces blog.

Z là một phương pháp xử lý xâu khá hay, ứng dụng phổ biến nhất của Z là dùng để tìm kiếm xâu (tìm các vị trí mà xâu A xuất hiện trong xâu B).

Thuật toán Z có đầu vào là một xâu, kết quả sau khi thực hiện là một mảng \(Z\) (được định nghĩa cụ thể ở dưới), từ mảng này có thể ứng dụng cho nhiều bài toán trên xâu khác.

Mô tả thuật toán

Cho xâu \(S\) với độ dài \(n\), thuật toán Z sẽ tạo ra mảng \(Z\) với ý nghĩa \(Z[i]\) là độ dài xâu con dài nhất bắt đầu từ \(i\) và là tiền tố của S. Định nghĩa một cách bài bản hơn, ta có \(Z[i]\) là số lớn nhất sao cho \(S[j] = S[i+j]\) với \(0 \leq j \leq Z[i]\). Ta gọi đoạn con như vậy là prefix-substring.

Duyệt \(i\) từ \(1\) đến \(n-1\) (mảng bắt đầu từ 0), ở mỗi vị trí ta quản lí một đoạn \([l, r]\), \(r\) lớn nhất có thể sao cho xâu con từ \(l\) tới \(r\) là tiền tố của xâu \(S\) (prefix) (Lưu ý là chỉ yêu cầu \(r\) lớn nhất chứ cả đoạn \([l, r]\) không cần phải lớn nhất). Ta sẽ tính \(Z[i]\) chung trong vòng lặp trên. Ban đầu \(l = r = 0\).

Giả sử ở i ta đã có đoạn \([l, r]\) cho vị trí i-1 và tính được tất cả các giá trị Z trước đó. Chia trường hợp để cập nhật l, r, và Z[i] như sau:

  • Nếu i > r, trong trường hợp này không có tiền tố nào bắt đầu trước i và kết thúc sau i, vì vậy ta gán lại \(l=i\), và cho \(r\) chạy từ \(i\) trở lên để tìm đoạn \([l,r]\) mới. Sau đó tính \(Z[i]=r-l+1\).
  • Trường hợp ngược lại, \(i \leq r\). Đặt \(k = i - l\), ta thấy xâu \(S[k...]\) và xâu \(S[i...]\) giống nhau ở ít nhất \(r - i + 1\) phần tử đầu, vì vậy có thể tận dụng \(Z[k]\) để tính \(Z[i]\). Ta có: \(Z[i] \geq min(Z[k],r-i+1)\).
    • Nếu \(Z[k]<r-i+1\), ta có \(Z[i]=Z[k]\) vì nếu \(Z[i]\) lớn hơn thì \(Z[k]\) đã phải có giá trị lớn hơn giá trị hiện tại.
    • Nếu \(Z[k] \geq r-i+1\), trong trường hợp này tiền tố bắt đầu từ \(i\) có thể vượt quá \(r\) nên ta gán lại \(l=i\) và cho \(r\) tiếp tục tăng để tìm đoạn \([l,r]\) mới. Sau đó cũng có \(Z[i]=r-l+1\) như trên.

Một số lưu ý:

  • Độ phức tạp của thuật toán là \(O(N)\), vì \(i\) và \(r\) luôn tăng trong quá trình chạy.
  • Không cần quan tâm tới giá trị của \(Z[0]\) (theo định nghĩa thì \(Z[0]=n\)).

Cài đặt

vector<int> z_algo(const string &s) {
    int n(s.size());
    vector<int> z(n);

    int l(0), r(0);
    for (int i=1; i<n; i++) {
        if (i > r) {
            l = r = i;
            while (r<n && s[r-l]==s[r]) r += 1;
            z[i] = r - l;
            r -= 1;
        } else if (z[i-l] < r-i+1) {
            z[i] = z[i-l];
        } else {
            l = i;
            while (r<n && s[r-l]==s[r]) r += 1;
            z[i] = r - l;
            r -= 1;
        }
    }

    return z;
}

Ứng dụng xâu khớp chuỗi

Bài toán: SUBSTR

Để tìm các vị trí chuỗi B xuất hiện trong chuỗi A, ta tạo một chuỗi S mới bằng cách nối đuôi B và A, có kèm theo một kí tự xen giữa:

\[S = B + "." + A\]

Có thể thay “.” bằng một kí tự bất kì, miễn là nó không xuất hiện trong A và B.

Sau đó dùng thuật toán bên trên để tính mảng \(Z\) cho xâu \(S\), các vị trí có chuỗi \(B\) xuất hiện thì sẽ có \(Z[i] = length(B)\).

Code: /code/80/

Các ứng dụng khác

Comments