Help: Tìm kiếm tên bài hát sử dụng queue

[tnk2412]

Mình có 1 bài tập lớn là tìm 1 bài hát trong 1 danh sách bài hát cho trước (khoảng 1000 bài hát, tên các bài hát lưu trong file text). Ví dụ: gõ từ khóa "love you forever" thì hiển thị ra các bài hát tìm được có tên gần đúng với từ khóa nhất. Cái quan trọng là thuật toán so sánh xâu con lớn nhất thì mình ko biết. Hix. Ai biết giúp mình với

[noname.cpp]

Đây là bài toán đối sánh chuỗi(string matching). Để xem xét độ tương tự của 2 chuỗi, có 2 phương pháp phổ biến:
- Dùng thuật toán "Edit distance". Thuật toán này đếm số phép biến đổi(xóa, thêm, thay thế 1 kí tự) tối thiểu để biến đổi chuỗi này thành chuỗi kia từ đó đo được độ tương tự của 2 chuỗi. Số phép biến đổi càng ít, hai chuỗi càng giống nhau.
- Dựa vào thuật toán "Longest Common Subsequence". Thuật toán này tìm chuỗi kí tự chung dài nhất của 2 chuỗi cần đối sánh(không cần liên tục) để từ đó đo độ tương tự của 2 chuỗi.

Trên mạng có rất nhiều tài liệu về 2 thuật toán này. Bạn có thể tìm kiếm với từ khóa là tên các thuật toán đó.

[tnk2412]

Đây là bài toán đối sánh chuỗi(string matching). Để xem xét độ tương tự của 2 chuỗi, có 2 phương pháp phổ biến:
- Dùng thuật toán "Edit distance". Thuật toán này đếm số phép biến đổi(xóa, thêm, thay thế 1 kí tự) tối thiểu để biến đổi chuỗi này thành chuỗi kia từ đó đo được độ tương tự của 2 chuỗi. Số phép biến đổi càng ít, hai chuỗi càng giống nhau.
- Dựa vào thuật toán "Longest Common Subsequence". Thuật toán này tìm chuỗi kí tự chung dài nhất của 2 chuỗi cần đối sánh(không cần liên tục) để từ đó đo độ tương tự của 2 chuỗi.

Trên mạng có rất nhiều tài liệu về 2 thuật toán này. Bạn có thể tìm kiếm với từ khóa là tên các thuật toán đó.
Cám ơn rất nhiều. Mình đang cần. Thx nhahttp://i12.photobucket.com/albums/a216/boa_myangel/blingeye.gif

[thanhhuy191188]

nếu như như vậy thì hai thuật toán này đều là thuật tóa quy hoạch động. thuật toán của bài tìm chuỗi con chung dài nhất , và thuật toán của bài thực hiện một số ít phép biến đổi xóa , thay thế , chèn để có hai chuỗi giống nhau.