NKPALIN - Chuỗi đối Xứng - Solution For SPOJ

Trang chủ » Tách Xâu đối Xứng » NKPALIN - Chuỗi đối Xứng - Solution For SPOJ

Có thể bạn quan tâm

Tutorial SPOJ Hướng dẫn và chia sẻ lời giải cho các problems trên vn.spoj.com
  • « No results found »
  • View more results »
    Navigation
  • Home
  • Categories
  • Search
  • Wiki
  • About Us
  • XML Feed
Tags: dp

Problem

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

https://oj.vnoi.info/problem/NKPALIN

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

Tutorial

Gọi F[i][j] là xâu con đối xứng dài nhất trong đoạn từ i đến j. Mảng này có thể tính bằng hai vòng for dễ.

Sau khi biết chiều dài dài nhất có thể của xâu con đối xứng (tức là F[0][size(s)-1]). Ta đệ quy tìm xâu này (dùng 4 biến i,j,L,R với i,j là hai đầu xâu s đang xét, L,R là hai đầu xâu cần tìm)

Submission

NKPALIN.cpp Hide View on Github Download Copy Nếu bạn thấy bài viết này hay, hãy share bài viết này cho mọi người nhé 😉.Share this post → Tweet

Related Posts

  • BONUS - VOI 2011 Phần thưởng (Categories: dp)
  • ZABAVA - ZABAVA (Categories: dp, math)
  • XUCXAC - Xúc xắc (Categories: dijkstra, dp, heap, data-structure)
  • WEATHER - Điều kiện thời tiết (Categories: tarjan, dfs, graph, dp, math)
  • VSTEPS - Steps - Bậc thang (Categories: dp)
  • VOSTRIBO - Tribonacci (Categories: matrix, math, dp)
  • VOSSEVEN - Bài toán số 7 (Categories: dp)
  • VDANGER - Nguy hiểm rõ ràng trước mắt (Categories: dijkstra, dp, graph)
« NKONEARC - Mạng máy tính NKPATH - Đường đi trên lưới »

Từ khóa » Tách Xâu đối Xứng