Kiểm tra chuỗi đối xứng

Đây cũng là một bài khá cơ bản trong Pascal.

Chuỗi đối xứng là chuỗi mà viết xuối hay viết ngược đều như nhau.

Trong bài này, mình sẽ giới thiệu các bạn hai cách.

Cách 1

Dựa vào đặc điểm của nó, ta sẽ dễ hiểu như sau. Với một chuỗi, ta viết ngược lại, nếu chuỗi viết ngược lại giống chuỗi ban đầu thì chuỗi ban đầu đối xứng (và dĩ nhiên chuỗi viết ngược lại cũng đối xứng). Dựa vào đó, ta có thuật toán sau

Code:

program chuoi_doi_xung;
uses crt;
var s,st:string; i:integer;
begin
 clrscr;
 write('nhap chuoi: ');readln(s);
 ss:='';
 for i:=length(s) downto 1 do
  st:=st+s[i]
 if s=st then writeln('chuoi doi xung.')
 else writeln('chuoi khong doi xung.');
readln;
end.

Cách 2

Dựa trên cách 1 ta có nhận xét sau: Chuỗi đối xứng phải có kí tự thứ i và kí tự thứ length(s)-i+1 bằng nhau. Ví dụ:
s=|a.1|a.2|a.3|a.4|...|a.n|
st=|a.n|...|a.4|a.3|a.2|a.1|
khi s=st thì a.1=a.n, a.2=a.n-1....
Như vậy sễ thấy công thức chung, a.i=a.length(s)-i+1 . Ta dựa vào đó để cải tiến thuật toán. Ta sẽ cho biế i chạy tiwf 1 đến length(s) div 2, nếu s[i]=s[length(s)-i+1] thì bỏ qua, ngược lại thì gán lại biến kiểm tra là false. Bài cụ thẻ sẽ như sau.

Code:

program chuoi_doi_xung;
uses crt;
var s:string; i:integer;bl:boolean;
begin
 clrscr;
 write('nhap chuoi: ');readln(s);
 bl:=true;
 for i:=1 to length(s) do
  if s[i]<>s[length(s)-i+1] then bl:=false;
 if bl=true then write('doi xung')
 else write('khong doi xung');
readln;
end.

bạn oi!Sửa "readlb" thanh "readln" cho mấy bạn khác khỏi bị sai.

bài như thế này là tốt lắm rồi. Nhưng bạn cần post nhiều bài căn bản như vậy hơn nữa

OK ok, mình đánh trực tiếp nên có lỗi, sorry, sửa lại liền

Littlelee làm bài này không sai nhưng câu lệnh for bị dư nhiều quá không cần thiết (bạn nên giới hạn vòng for lại phân nửa chiều dài xâu thôi)

Cách 1:

Code:

Function          Xaudoixung(S:String): boolean;
Var                i,n : integer;
Begin
                      N:=length(S);
                      For i := 1 to (n div 2) do
                      If s[i]<>s[n+1-i] then
                      Begin
                                  Xaudoixung:=false;
                                  Exit;
                      End;
                      Xaudoixung:=True;
End;

Cách 2:

Code:

Function      palindrome(s : string) : boolean;
Var            i, j : integer;
begin
                i := 1;
                j := length(n);
                while i<=j do
                begin
                            if s[i] <> s[j] then
                            begin
                                          palindrome := false;
                                          exit;
                          end;
                          inc(i);
                          dec(j);
                  end;
                  palindrome := true;
End;

tớ lại có một ý tưởng khác
ta sẽ for i từ 1 đến độ dài chuỗi
tại i ta xét xem nó có phải là tâm kí tự đối xứng ko or nhóm tâm 2 kí tự của chuỗi con nào ko
vì vậy ta chỉ tốn 2 dòng for
với dòng for thứ 2 chỉ tốn nhiều nhất length(s) div 2 thôi
đồng thời dòng for thứ nhất, nếu ta dùng nhánh cận thì ta ko cần chạy tới length(s) đâu

code tớ chưa đánh xong nên chưa đưa lên được

đây là code của tớ:

{chuoi doi xung}
const inp='chuoi.inp';
out='chuoi.out';
maxint=100000;
var i,j,n,max:longint;
s,sl:ansistring;
f:text;
procedure tam1(i:longint);
begin
j:=0;
while (i-j>0)and(i+j<=n)and(s[i-j]=s[i+j]) do inc(j);
if j*2-1>max then max:=j*2-1;
end;
procedure tam2(i:longint);
begin
j:=0;
while (i-j+1>0)and(i+j<=n)and(s[i-j+1]=s[i+j]) do inc(j);
dec(j);
if j*2>max then max:=j*2;
end;
begin
assign(f,inp);
reset(f);
readln(f,n);
repeat
readln(f,sl);
if sl<>'' then s:=s+sl;
until sl='';
close(f);
assign(f,out);
rewrite(f);
for i:=1 to n-1 do
begin
if (i>1)and(s[i-1]=s[i+1]) then tam1(i);
if s[i]=s[i+1] then tam2(i);
if n-i<max div 2 then break;
end;
if max=0 then max:=1;
writeln(f,max,#32);
close(f);
end.
[code]