Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba

nhut95 viết:

QUOTE:
Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba

Bài này bạn chỉ cần tìm xâu con chung dài nhất của xâu đó với xâu ngược lại của nó thôi..
Tỉ dụ input là abcdecba thì bạn tìm xâu con chung lớn nhất của xâu abcdecba và xâu abcedcba, sau đó truy vết là ra kết quả.

Cám ơn bạn nhe.

Bom viết:

QUOTE:
nhut95 viết:

QUOTE:
Đề bài: Cho một xâu ký tự S có độ dài không quá 5000 ký tự. Hãy tìm chuỗi con đối xứng dài nhất từ chuỗi đã cho. (Chuỗi con đó được lấy bằng cách xoá một vài ký tự trong chuỗi S).
Yêu cầu: Thời gian chạy không quá 2 giây.
Input: file input có tên PALIN.INP gồm:
- Dòng 1 gồm số nguyên n: đội dài chủa chuỗi.(1<=n<=5000).
- Dòng 2 là chuỗi ký tự. Không có dấu cách.
Output: file output có tên PALIN.OUT gồm chuỗi con đối xứng dài nhất tìm được.
Ví dụ:

PALIN.INP:
7
abcdbka
PALINH.OUT:
abcba hoặc abdba

Bài này bạn chỉ cần tìm xâu con chung dài nhất của xâu đó với xâu ngược lại của nó thôi.:).
Tỉ dụ input là abcdecba thì bạn tìm xâu con chung lớn nhất của xâu abcdecba và xâu abcedcba, sau đó truy vết là ra kết quả.

Nhưng với 5000 mà O(N^2) thì...

Có thể giảm xuống N^2 div 2 bằng cách gọi F[i,j] là độ dài chuỗi con dối xứng dài nhất của đoạn S[i..j]

@conmachua: O(n^2 div 2) thì vẫn là O(n^2)

đâu có liên wan jì đâu nhỉ??? :s

5000 mà n^2 thì có sao đâu. Thời gian yêu cầu là 2s mà.