Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X. Một xâu được gọi là đối xứng (palindrome) nếu như khi đọc xâu này từ phải sang trái cũng thu được xâu ban đầu. Bài toán: Cho một xâu ký tự S (chỉ gồm các ký tự chữ cái latin) hãy tìm một xâu con đối xứng dài nhất của xâu S. Dữ liệu vào:
- Một dòng duy nhất chứa xâu S.
Dữ liệu ra:
- Mộ dòng duy nhất ghi độ dài sâu con dài nhất tìm được.
Ví dụ:
Dữ liệu vào:
Dữ liệu ra:
Giới hạn:
- Độ dài xâu S không quá 2000 ký tự.
Nội dung Text: Bài toán chuỗi con đối xứng dài nhất - Bài toán chuỗi con đối xứng dài nhất 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 quả Gồm một dòng duy nhất là một chuỗi con đối xứng dài nhất của chuỗi 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 vào lmevxeyzl Kết quả level Ta sẽ chuyển bài toán về một bài toán quy hoạch động cơ bản là: Bài toán tìm chuỗi con chung dài nhất Với dữ liệu vào là S1. Ta tạo chuỗi S2 là chuỗi ngược của S1bằng cách chép các phần tử của chuỗi S1 vào chuỗi S2 theo thứ tự ngược lại. Sau đó ta sẽ tìm chuỗi con chung dài nhất của S1 và S2. Ta chỉ cần tìm chuỗi con chung dài nhất của một phần của S1 và nghịch đảo phần còn lại, tức là ta chỉ xét một phần của bảng phương án với i+j
- Ta có bảng phương án Khi đó chuỗi con chung dài nhất là le của S14=“lmev” và S24=”lzye” (hoặc S13=”lme” và S25=”lzyex”) Khi ta truy vết để tìm chuỗi con chung ta sẽ kiểm tra xem chuỗi đối xứng của chúng ta là lẻ hay chẵn (số kí tự). Nếu i+j=chiều dài của S1, tức là 2 kí tự đối xứng đứng liên tiếp nhau trong S1, vì vậy chuỗi đối xứng là chẵn. Ngược lại, tức là mọi i+j
-
define Output "doixung.out" char S1[2000],S2[2000],S[2000]; int B[2001][2001],T[2001][2001]; int L,MaxP; void GetInput() { ifstream fi(Input); fi>>S1; fi.close(); L=strlen(S1); for (int i=0; i - T[i][j]=1; } else { B[i][j]=B[i][j-1]; T[i][j]=-1; } } } void Trace() { int maxP=0; int i,j; for (i=1; imaxP) { maxP=B[i][L-i]; j=L-i; } i=L-j; int k=i; int Ls=maxP; bool even=false; while (i>0 && j>0) { if (T[i][j]==0) { if (i+j==L) even=true; S[Ls]=S1[i-1]; i; j--; } else if (T[i][j]==1) i--; else j--; } j=maxP-1;
- if (!even) S[maxP++]=S1[k]; while (j>=0) S[maxP++]=S[j--]; S[maxP]=0; } int main() { GetInput(); Optimize(); Trace(); PutOutput(); return 0; }
Để kiểm tra xâu đối xứng ta chỉ cần xét các cặp ký tự đối xứng nhau ở 2 bên bằng cách dùng cặp chỉ số left, right Code 1 : include "stdio.h"
include "ctype.h"
include "string.h"int doixung1(char c[]){ int l = 0, r = strlen(c) - 1;
while(l <= r){
if(c[l] != c[r]){
return 0;
}
++l; --r;
}
return 1;
}
int main(){ char s[1000] = "28techhcet82";
if(doixung1(s)){
printf("%s doi xung !\n", s);
}
else{
printf("%s khong doi xung !\n", s);
}
return 0;
}
Output : 28techhcet82 doi xung ! Cách thứ 2 là bạn có thể so sánh kí tự ở chỉ số i với kí tự đối xứng với nó ở chỉ số n - i - 1 với n là số lượng ký tự trong xâu. Code 2: include "stdio.h"
include "ctype.h"
include "string.h"int doixung2(char c[]){ int n = strlen(c);
for(int i = 0; i < n / 2; i++){
if(c[i] != c[n - i - 1]){
return 0;
}
}
return 1;
}
int main(){ char s[1000] = "28techhcet82";
if(doixung2(s)){
printf("%s doi xung !\n", s);
}
else{
printf("%s khong doi xung !\n", s);
}
return 0;
}
Output : 28techhcet82 doi xung !
2. Lật ngược xâu ký tự Để lật ngược một xâu ký tự trong C bạn làm tương tự cách kiểm tra xâu đối xứng Trong C có hàm strrev() được dùng để lật ngược một xâu nhưng không phải là hàm chuẩn nên không thể dùng ở mọi trình biên dịch C. | 
