Classic problems

“Classic” ở đây với nghĩa là những bài có phát biểu ngắn gọn và có thể ứng dụng trong các bài toán lớn khác

Updated 6/4/2017

Lưu ý: 
+ Substring / Subarray là dãy con liên tục 
+ Subsequence là dãy con có thể không liên tục

Dãy số

– Tìm Subsequence dài nhất của dãy số (LIS – Longest Increasing Subsequence) O(NlogN): code mẫu

String

– So khớp chuỗi KMP O(N+M): code mẫu , bài tập

– Tìm Subsequence chung dài nhất của 2 xâu/dãy (LCS – Longest Common Subsequence ) O(N*M) : bài tập

– Tìm số bước biến đổi (delete, add, replace) ít nhất để biến xâu này thành xâu kia (String Alignment, Edit Distance) O(N*M)  : bài tập

Palindrome

– Tìm Palindrome Subsequence dài nhất trong một xâu O(N*N): bài tập

– Thêm vào cuối xâu S ít kí tự nhất để được xâu Palindrome O(N): bài tập

– Thêm vào xâu S ít kí tự nhất để được xâu Palindrome O(N*N): bài tập

– Biến đổi xâu S (delete, insert, replace) ít thao tác nhất để được xâu Palindrome O(N*N) : bài tập

– Đếm số Palindrome Subsequence trong xâu S O(N*N): bài tập

Suffix Array

– Tìm Substring dài nhất xuất hiện ít nhất 2 lần trong 1 xâu O(Nlog^2N): bài tập

– Tìm Substring chung dài nhất của 2 xâu (LCS – Longest Common Substring) O(Nlog^2N): bài tập

– Tìm Substring chung dài nhất của M xâu trong N xâu cho trước (M <= N)

Graph

– Kiểm tra xem một đồ thị  liên thông vô hướng có phải là một Clique hay không: E = V*(V-1)/2: bài tập

– Tìm thứ tự topo của một đồ thị có hướng không chu trình (DAG)

– Tìm tất cả thứ tự topo của một đồ thị có hướng không chu trình (DAG)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s