Giúp em bai` này với.... Biến đổi xâu

[hangngand]

Một xâu gọi là xâu đối xứng (plalindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái dều nhu nhau

YÊU CẦU Cho một xâu s, hãy tìm số kí tự ít nhất cần thêm vào S dể S trở thành xâu đối xứng
DỮ LIỆU vào file inp chứa xâu S ( tối đa 100 kí tự)
KẾT QUẢ la số kí tự ít nhất cần chèn vào S
VÍ DU:

inp out
abc 2


Anh Chị chỉ giùm em nhe''. thanks nhieu``````:emlaugh::emlaugh:

[MinhPhuc123]

Bạn search cái "những bài quy hoạch động kinh điển" thì sẽ có đáp án. Mình nói qua, bạn đọc tài liệu sẽ hiểu rõ hơn:
Cách 1: Quy hoạch động
Công thức quy hoạch động hơi lạ, nhìn thì dễ hiểu nhưng cài đặt được hay không thì bạn phải nghĩ ngợi kha khá [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
F[i,j]: số kí tự ít nhất cần thêm vào để xâu i->j trở thành đối xứng
S=S[j] thì F[i,j]=F[i+1,j-1]
S<>S[j] thì F[i,j]=min(F[i+1,j],F[i,j-1])+1
Kq bài toán là F[1,n] với n là length(s)
Vì công thức hơi lạ nên các bạn có thể cài theo đệ quy cũng được, hoặc nếu nghĩ được điều gì đúng đắn thì chuyển sang qhd mà làm [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Cách 2: đơn giản hơn
Đảo ngược xâu S thành xâu X. Tìm xâu con chung của S và X (gọi là Y), số kí tự cần thêm vào là length(S)-length(Y).
Các bạn thử cài đặt theo cách 1 nhé, nếu có gì khó khăn thì lên diễn đàn hỏi. Cần thiết thì mình có thể cho các bạn xem code, nhưng mình nghĩ là học sinh lớp Tin mới giải bài này chứ lớp khác không bao giờ, nên các bạn tự code là tốt nhất, ngấm hơn nhiều so với việc đọc code của người khác.

[trungtrinh]

cho e code cách 2 dj. thanks nhiều [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]:d

Hơi thất vọng! Mình vừa nói bên trên là các bạn cần tự code đi đã rồi hãy hỏi, thế mà post bài chưa được 15' đã hỏi rồi. Mà lại còn yêu cầu code cách 2. Mình hỏi thật, bạn post bài lên diễn đàn để xin code hay muốn có thêm chút gì đó vào đầu? Code cách 1 thì mình có, còn cách 2 chưa làm.

[thegioibang]

Theo cách 2:
S='abca'
->X='acba'
Xâu con chung là Y='aca' hoặc 'aba', vậy cần thêm vào 1. Theo em nghĩ:
abcacba mới tạo được 1 xâu đối xứng, không biết em có nhầm lần gì không anh giải thích giúp :|

[BaoNgoc99]

Theo cách 2:
S='abca'
->X='acba'
Xâu con chung là Y='aca' hoặc 'aba', vậy cần thêm vào 1. Theo em nghĩ:
abcacba mới tạo được 1 xâu đối xứng, không biết em có nhầm lần gì không anh giải thích giúp :|

Thêm vào 1 kí tự ta được: abcba đã là xâu đối xứng.

[dinhhaianh091]

Thêm vào 1 kí tự ta được: abcba đã là xâu đối xứng.

Ờ, em hiểu rồi! Thuật toán này hay nhỉ [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[NgocAnhs]

hjx !! tại em chưa hoc quy hoach động mà cách 2 em thử chạy mà không được. anh cho em xin code bài hai di. thanks nhiều [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG][IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]:[IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]v

[benjamin239]

Bài này cả 2 cách đều làm = quy hoạch động, nếu bạn chưa học qhd thì sao lại muốn làm bài này?