Hướng dẫn cho Xâu con chung dài nhất

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.9}}}}}$
</button>

$\color{#ff7500}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$ $\color{#ff7500}{\text{Và sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu với thuật của mình và thu được bài học cho mình}}$ $\color{#ff7500}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ [ở đây](https://www.facebook.com/SPectiar2k/)

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{orange}{\text{Mục lục}}$
</button>

$\color{#300000}{\text{Hint 1 <Cày trâu>}}$

$\color{#903030}{\text{<Duyệt toàn tập>}}$ Xét toàn bộ các xâu con $subs \subseteq S$, với mỗi xâu $subs$ ta xét toàn bộ xâu con $subt \subseteq T$

Nếu $subs = subt$ thì $subs$ là xâu con chung có độ dài $subs.size$

Kết quả bài toán là $res = max(subs.size)$

$\color{#7f5f3f}{\text{Phân tích độ phức tạp}}$

Gọi $n = s.size$ và $m = t.size$

Có $2^n$ cách chọn xâu $subs$ và mỗi xâu như thế có $2^m$ cách chọn $subt$ nên độ phức tạp tông thể là $\Theta(2^n \times 2^m)$

$\color{#903030}{\text{Cải tiến bằng cách chọn các xâu cùng độ dài}}$

Gọi $k = min(s.size, t.size)$, ta chỉ xét các xâu $subs$ và $subt$ có $subs.size = subt.size$

Với độ dài $l$ ta có $\binom{n}{l}$ cách chọn xâu $subs$ và $\binom{m}{l}$ cách chọn $subt$ nên độ phức tạp tổng thể là $\Theta(\binom{n + m}{n})$

Việc chứng minh chi tiết xin nhường bạn đọc xem như bài tập

Gợi ý $\binom{n + m}{n} = \underset{l \in [0, k]}{\Sigma}\binom{n}{l} \times \binom{m}{l}$

$\color{#903030}{\text{Cải tiến bằng nhánh cận: chọn các xâu có cùng tiền tố}}$

Khi ta xét đến chữ thứ $l$, nếu $subs[l] \neq subt[l]$ thì ta loại ngay luôn

Trường hợp xấu nhất khi toàn bộ xâu chỉ gồm 1 kí tự và càng trở nên hiệu quả khi 2 xâu càng nhiều phần tử phân biệt

$\color{#300000}{\text{Hint 2 <Quy hoạch động>}}$

$\color{#903030}{\text{Định nghĩ hàm quy hoạch động:}}$ $f[i][j]$ là xâu con chung của đoạn $s[1 \dots i]$ và $t[1 \dots j]$

Khi $i = 0$ thì ta đang xét xâu $s$ rỗng nên $f[i = 0][j] = \{\}$

Khi $j = 0$ thì ta đang xét xâu $t$ rỗng nên $f[i][j = 0] = \{\}$

Khi $s_i = t_j$ thì ta sẽ nối thêm 1 kí tự $s_i$ vào $f[i - 1][j - 1]$ (xâu con chung lớn nhất trước khi xét tới phần tử $s_i$ và $t_j$)

Khi $s_i \neq t_j$ thì ta sẽ có 2 lựa chọn

Bỏ qua $s_i$ thì ta được xâu con chung $f[i - 1][j]$

Bỏ qua $t_j$ thì ta được xâu con chung $f[i][j - 1]$

$\color{#903030}{\text{Công thức quy hoạch động:}}$

$f[i][j] = \{\}$ khi $i = 0$ hoặc $j = 0$

$f[i][j] = f[i - 1][j - 1] + s_i$ khi $s_i = t_j$

$f[i][j] = max(f[i - 1][j], f[i][j - 1])$ khi $s_i \neq t_j$

$\color{#7f5f3f}{\text{Phân tích độ phức tạp}}$

Số trạng thái là $O(n \times m)$

Chi phí chuyển là $O(f[i][j].size) = O(min(n, m))$

Độ phức tạp là $O(n \times m \times min(n, m))$

$\color{#300000}{\text{Hint 3 <Giảm chiều quy hoạch động>}}$

$\color{#903030}{\text{Định nghĩ hàm quy hoạch động:}}$ $f[i][j]$ là độ dài xâu con chung của đoạn $s[1 \dots i]$ và $t[1 \dots j]$

Khi $i = 0$ thì ta đang xét xâu $s$ rỗng nên $f[i = 0][j] = 0$

Khi $j = 0$ thì ta đang xét xâu $t$ rỗng nên $f[i][j = 0] = 0$

Khi $s_i = t_j$ thì ta sẽ nối thêm 1 kí tự, nên ta tăng thêm 1 độ dài $f[i - 1][j - 1]$ (xâu con chung lớn nhất trước khi xét tới phần tử $s_i$ và $t_j$)

Khi $s_i \neq t_j$ thì ta sẽ có 2 lựa chọn

Bỏ qua $s_i$ thì ta được xâu con chung độ dài $f[i - 1][j]$

Bỏ qua $t_j$ thì ta được xâu con chung độ dài $f[i][j - 1]$

$\color{#903030}{\text{Công thức quy hoạch động:}}$

$f[i][j] = 0$ khi $i = 0$ hoặc $j = 0$

$f[i][j] = f[i - 1][j - 1] + 1$ khi $s_i = t_j$

$f[i][j] = max(f[i - 1][j], f[i][j - 1])$ khi $s_i \neq t_j$

Giờ ta chỉ việc truy vết ngược lại từ mảng quy hoạch động trên để tìm kết quả

$\color{#300000}{\text{Hint 4 <Truy vết>}}$

$\color{#903030}{\text{Việc di chuyển: }}$ Xét $x$ và $y$ là cặp vị trí đang xét trên xâu $s$ và $t$. Với $res$ là xâu kết quả

Khi $x = 0$ hoặc $y = 0$ ta thu xâu rỗng nên ta sẽ dừng

Khi $s_x = t_y$ thì nối thêm $s_x$ lên đầu $res$ và di chuyển sang ô $(x, y) = (x - 1, y - 1)$

Khi $s_x \neq t_y$ ta sẽ xét 3 trường hợp

Khi $f[x - 1][y] > f[x][y - 1]$ thì bạn đi sang $(x = x - 1)$ sẽ có kết quả tối ưu hơn

Khi $f[x - 1][y] < f[x][y - 1]$ thì bạn đi sang $(y = y - 1)$ sẽ có kết quả tối ưu hơn

Khi $f[x - 1][y] = f[x][y - 1]$ thì bạn đi đâu trong 2 cách trên cũng được

$\color{#903030}{\text{Cải tiến: }}$

Việc chèn kí tự lên đầu xâu tốn $O(res.size)$

Ta có thể chèn ra sau xâu sau đó đảo ngược lại nó

$\color{#903030}{\text{Phân tích độ phức tạp: }}$

$x$ sẽ di chuyển $O(n)$ và $y$ sẽ di chuyển $O(m)$ nhưng di chuyển song song nhau nên mát $O(n + m)$

Chi chí chuyển là $O(res.size)$ (với việc chèn đầu) $\Rightarrow$ $O(1)$ (với việc chèn sau)

Việc đảo ngược xâu kết quả $O(res.size)$ (sau quá trình chèn sau)

Độ phức tạp là $O(n + m + res.size)$

$\color{#009933}{\text{Preference Accepted Code }}$: Quy hoạch động, Truy vết

$^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times m)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n \times m)\ \color{#7f5f3f}{\text{memory}}}}$

C++

int main()
{
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();
    vector<vector<int> > f(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (s[i - 1] == t[j - 1])
                f[i][j] = f[i - 1][j - 1] + 1;
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }

    string res;
    for (int x = n, y = m; x > 0 && y > 0; )
    {   
        if (s[x - 1] == t[y - 1])
        {
            res += s[x - 1];
            x--;
            y--;
        }
        else 
        {
            if (f[x - 1][y] > f[x][y - 1])
                x--;
            else 
                y--;
        }
    }

    reverse(all(res));
    cout << res;
    return 0;
}

$\color{#9000ff}{\text{Question}}$

Bạn có thể giải bài này với độ phức tạp bộ nhớ $O(n)$ không ?

$\color{#903030}{\text{Gợi ý:}}$ Chia để trị (Divide and conquer)

Bình luận

Không có bình luận nào.

Hướng dẫn cho Xâu con chung dài nhất

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

\(\color{#300000}{\text{Hint 2 <Quy hoạch động>}}\)

\(\color{#300000}{\text{Hint 3 <Giảm chiều quy hoạch động>}}\)

\(\color{#300000}{\text{Hint 4 <Truy vết>}}\)

\(\color{#009933}{\text{Preference Accepted Code }}\): Quy hoạch động, Truy vết

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times m)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n \times m)\ \color{#7f5f3f}{\text{memory}}}}\)

\(\color{#9000ff}{\text{Question}}\)

Bình luận