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

Overview

C11STR2 - Tiền tố và hậu tố

solution.md

Xâu C có dạng như sau:

Xâu A _____________________
                ________________________ Xâu B
                \_________/
                         Phần chung của A và B

Ta cần tìm sao cho phần chung của A và B là dài nhất có thể. Ta thấy phần đó chính là hậu tố của A và là tiền tố của B. Có thể dùng hash để giải bài này, tuy nhiên cũng có thể dùng thuật toán Z như sau:

Nối 2 xâu B và A (B đứng trước), cách nhau bởi 1 kí tự đặt biệt không xuất hiện trong cả 2 xâu. Sau đó chạy thuật toán Z trên xâu mới. Tìm vị trí đầu tiên mà Z ở đó đúng bằng độ dài từ đó đến cuối xâu. Xem thuật toán Z để hiểu ý nghĩa mảng Z.

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> z_algo(const char *s, int n) {
    vector<int> z(n);

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

    return z;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string a, b; cin >> a >> b;
    string c = b + " " + a;
    vector<int> z = z_algo(c.data(), c.size());
    int n = a.size(), m = b.size(), k = z.size();
    for (int i=m+1; i<k; i++) if (z[i] == n-(i-m-1)) {
        cout << a.substr(0, i-m-1) + b;
        return 0;
    }
    cout << a + b;
    return 0;
}
Comments