Chuỗi đối Xứng (NKPALIN) | Trái Táo đỏ

Nguồn 

http://vn.spoj.com/problems/NKPALIN/

Đề bài

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn

Chuỗi s có độ dài không vượt quá 2000.

Ví dụ

Dữ liệu mẫu lmevxeyzl   Kết qủa level

Hướng dẫn

Dựa vào tính chất của palindrome, dễ thấy rằng chuỗi con đối xứng dài nhất trong xâu s chính là xâu con chung dài nhất của xâu s với xâu đảo của nó. Áp dụng thuật toán bài QBSTR tìm xâu con chung dài nhất.

Lời giải

Các bạn tham khảo tại đây.

Chia sẻ

• X
• Facebook

Thích Đang tải...

Bài viết liên quan

Điều hướng bài viết ← Dãy con chung không liền kề dài nhất (LNACS) VOI 2014 – Dãy con chung bội hai dài nhất (LCS2X) → Tìm kiếm Search Lịch Tháng Tám 2015

H	B	T	N	S	B	C
1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Th9 » Bình luận mới nhất

	qduynl trong THÔNG BÁO TỪ BAN QUẢN TRỊ BLOG
	Phát Lưu Nguyễn trong THÔNG BÁO TỪ BAN QUẢN TRỊ BLOG
	qduynl trong THÔNG BÁO TỪ BAN QUẢN TRỊ BLOG
	Phát Lưu Nguyễn trong THÔNG BÁO TỪ BAN QUẢN TRỊ BLOG
	qduynl trong THÔNG BÁO TỪ BAN QUẢN TRỊ BLOG

Meta

• Tạo tài khoản
• Đăng nhập
• RSS bài viết
• RSS bình luận
• WordPress.com

• Đăng lại
• Theo dõi Đã theo dõi
  • Trái táo đỏ
  Theo dõi ngay
  • Đã có tài khoản WordPress.com? Đăng nhập.
• • Trái táo đỏ
  • Theo dõi Đã theo dõi
  • Đăng ký
  • Đăng nhập
  • URL rút gọn
  • Báo cáo nội dung
  • Xem toàn bộ bài viết
  • Quản lý theo dõi
  • Ẩn menu

%d Tạo trang giống vầy với WordPress.comHãy bắt đầu