Hướng Dẫn Cho Xâu Con Chung Dài Nhất - LQDOJ: Le Quy Don ...

Có thể bạn quan tâm

Trang chủ
Bài tập
Bài nộp
Thành viên
Kỳ thi
Nhóm
Giới thiệu
- Máy chấm
- Khóa học
- Đề xuất ý tưởng
- Đề xuất bài tập
- Markdown Editor
- Báo cáo tiêu cực
- Báo cáo lỗi

Tiếng Việt

Tiếng Việt English

Đăng nhập

Đăng ký

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>

<header> 1. Bài giải </header> Cày trâu Quy hoạch động Giảm chiều qhd Truy vết Code Question

$\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++intmain() { strings,t; cin>>s>>t; intn=s.size(); intm=t.size(); vector<vector<int>>f(n+1,vector<int>(m+1,0)); for(inti=1;i<=n;++i) { for(intj=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]); } } stringres; for(intx=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; return0; } $\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.

Từ khóa » Thuật Toán Tìm Xâu Con Chung Dài Nhất

Hướng Dẫn Cho Xâu Con Chung Dài Nhất - LQDOJ: Le Quy Don ...

Tiếng Việt

Đăng nhập

Đăng ký

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>}}\)

Bình luận

Bài Toán Xâu Con Chung Dài Nhất C/C++

Bài Toán Chuỗi Con Chung Dài Nhất – Wikipedia Tiếng Việt

Các Cách Tiếp Cận Bài Toán LCS - Longest Common Subsequence.

QBSTR - Xâu Con Chung Dài Nhất - VietCodes

Bài 1 Xâu Con Chung Dài Nhất. - YouTube

Tìm Chuỗi Con Chung Dài Nhất - Gists · GitHub

Quy Hoạch động Tìm Xâu Con Chung độ Dài Lớn Nhất

Tìm Xâu Con Chung Dài Nhất Của Hai Xâu - Tài Liệu Text - 123doc

Bài Toán Tìm Chuỗi Con Chung Dài Nhất - TaiLieu.VN

Bài Toán Tìm Chuỗi Con Chung Dài Nhất Pdf - Tài Liệu Text - 123doc

Tìm Dãy Con Chung Dài Nhất Của Hai Dãy Số - Dạy Nhau Học

Bài Toán Xâu Con Chung Dài Nhất - Wikiwand

Liên Hệ