Chuyên đề Bồi dưỡng học sinh giỏi Tin học

 CHUYÊN ĐỀ XÂU BỒI DƯỠNG HSG TIN HỌC 
Để xử lý các chuỗi văn bản, Pascal đưa ra một kiểu dữ liệu mới gọi là xâu ký tự và được 
định nghĩa bằng từ khóa STRING. Xâu ký tự là dữ liệu bao gồm một dãy các ký tự trong 
bảng mã ASSCII. Tuy nhiên độ dài của String tối đa chỉ 255 mà thực tế thì ta thường gặp 
xâu có độ dài rất lớn cỡ hàng ngàn, vậy có cách nào để có thể khắc phục được điều đó, 
chúng tôi xin trình bày một số nội dung mà chúng tôi đã tìm hiểu và vận dụng có hiệu quả 
trong quá trình giảng dạy và bồi dưỡng đội tuyển.
I. CÁCH KHAI BÁO VÀ TRUY XUẤT ĐẾN PHẦN TỬ XÂU
1. Cách khai báo:
 Var: STRING[độ dài của xâu];
 - Xâu ký tự trong bộ nhớ nó chiếm số byte bằng số ký tự cực đại được khai báo cộng 
với byte đầu tiên chứa số ký tự hiện có của xâu. Độ dài tối đa của xâu ký tự là 255.
 - Ngoài ra có các kiểu khai báo khác của xâu như:
 + Shortstring: Chính là String.
 + longstring: là mảng ký tự có kiểu char. Thông thường kiểu char có kích thước 
16 bit nên mảng có kích thước tối đa 16 bit = 65535 ký tự.
 + ansistring (chỉ có trong free pascal mà không có trong turbo pascal) có kích 
thước gần 2GB = 230 B nên thường được xem là vô hạn.
2. Cách nhập/xuất:
 Cách đọc hay viết kiểu STRING cũng tương tự như các kiểu dữ liệu khác, ta sử dụng 
các thủ tục READ, hoặc WRITE.
 Ví dụ: Readln(st); Writeln(st);
3. Truy cập từng phần tử của xâu ký tự:
 Việc truy cập đến phần tử trong xâu tương tự mảng 1 chiều được thông qua tên biến 
kiểu STRING và chỉ số của nó
 Ví dụ: St := 'Le Thanh Lam'; write(st[4]);
 -> Kết quả: cho ra chữ T.
II. CÁC THAO TÁC TRÊN XÂU KÝ TỰ
1. Phép cộng xâu:
 Ví dụ: st1:=’tin’; st2:=’ hoc’; St=st1 + st2; 
 -> St = ‘tin hoc’
2. Phép so sánh: 
 Hai xâu ký tự có thể so sánh với nhau bằng các phép so sánh =, >, <
 Nguyên tắc so sánh thực hiện như sau, chúng sẽ đem từng ký tự tương ứng với nhau 
để so sánh, xâu nào có ký tự có số thứ tự trong bảng mã ASCII lớn hơn thì xâu đó lớn hơn.
 Hai xâu ký tự được gọi là bằng nhau khi chúng hoàn toàn giống nhau (có độ dài như 
nhau).
 Ví dụ: st1:=’tin’; st2:=’ hoc’; khi đó st1>st2 
3. Các thủ tục và hàm chuẩn xử lý xâu ký tự
a. Hàm length(st): cho độ dài thực của xâu ký tự st
 Ví dụ: st:=’tin hoc’ thì LENGTH(st) cho bằng 7.
b. Hàm upcase(ch): Cho ký tự hoa của ký tự ch
 Ví dụ: ch:= 'a'; ch:= upcase(ch) ® ch = 'A'
 Ví dụ: Viết đoạn chương trình nhập vào một xâu ký tự. Đổi xâu đó sang chữ in hoa rồi 
in kết quả ra màn hình
var s,s1:string; i:integer; readln(s);
 while s[1]=' ' do delete(s,1,1);
 while s[length(s)]=' ' do delete(s,length(s),1);
 while pos(' ',s)0 do delete(s,pos(' ',s),1);
 write(s);
 readln;
end.
g. Thủ tục INSERT(st1, st2, pos): Thủ tục cho kết quả bằng cách chèn xâu ký tự có tên là 
st1 vào xâu st2 tại vị trí pos, những ký tự đứng sau pos sẽ được dời về phía sau của xâu ký 
tự st2.
 Ví dụ: st1:= ‘tin ‘; st2:=’hoc kho’; INSERT(st1,st2,5) ® st2=’hoc tin kho’;
 Ví dụ: Viết đoạn chương trình nhập vào 3 xâu s1, s2, s (với xâu s1 xuất hiện một và 
chỉ đúng 1 lần trong xâu s). Tìm và thay thế xâu s1 thành xâu s2 trong xâu s.
 Chẳng hạn: s1 := 'hoc'; s2:= 'bai tap'; s :='hoc tin hoc'; kết quả sau khi thay thế s1 
thành s2 là s = 'bai tap tin hoc'
var s1,s2,s: string; i:byte;
begin
 write('nhap s1:');
 readln(s1);
 write('nhap s2:');
 readln(s2);
 write('nhap xau s:');
 readln(s);
 i:= pos(s1,s);
 delete(s,i,length(s1));
 insert(s2,s,i);
 write(s);
 readln;
end.
h. Thủ tục STR(value, st): Thủ tục này thực hiện việc chuyển đối giá trị kiểu số(value) sang 
dạng xâu ký tự và gán cho biến st.
 Ví dụ: n:=2014; STR(n,st) sẽ cho kết quả xâu st là: st=’2014’;
i. Thủ tục VAL(st, value,code) đổi một xâu ký tự st sang dạng số và gán cho biến value, nếu 
biến đối thành công thì code sẽ nhận giá trị bằng 0. ngược lại thì cho giá trị khác không
 Ví dụ: VAL(‘2014’,value,code) lúc này code sẽ nhận giá trị bằng 0 và value=2014
 Ví dụ: Viết đoạn chương trình nhập vào số tự nhiên a có n con số. Hãy tạo ra số mới 
b từ số a bằng cách in ngược có số xuất hiện trong a. Chẳng hạn số a = 123 thì b=321
var a,b:Qword; s,s1:string; i,code:longint;
begin
 write('nhap a:');
 readln(a);
 str(a,s);
 s1:='';
 for i:=length(s) downto 1 do s1:=s1+s[i];
 val(s1,b,code);
 write(b); i:=length(s1); nho:=0; s:='';
 while i>=1 do
 begin
 x:=ord(s1[i]) - ord('0');
 y:=ord(s2[i]) - ord('0');
 z:=x+y+nho;
 s:= chr(z mod 10 + ord('0')) + s;
 nho:= z div 10;
 dec(i);
 end;
 Add:=s;
end;
{======Phép trừ ===========}
function sub1(s1,s2:string):string;
var i,nho,z,x,y:longint; s:string;
begin
 while length(s1)<length(s2) do s1:='0'+s1;
 while length(s2)<length(s1) do s2:='0'+s2;
 i:=length(s1); nho:=0; s:='';
 while i>=1 do
 begin
 x:=ord(s1[i]) - ord('0');
 y:=ord(s2[i]) - ord('0');
 z:=x-y-nho;
 if z<0 then
 begin
 z:=z+10;
 nho:=1;
 end
 else nho:=0;
 s:= chr(z + ord('0')) + s;
 dec(i);
 end;
 sub1:=s;
end;
{=================}
 // Với trường hợp số bị trừ nhỏ hơn số trừ ta thực hiện hàm sau:
function sub(s1,s2:string):string;
begin
 if length(s1) > length(s2) then sub:=sub1(s1,s2)
 else
 if length(s2)>length(s1) then sub:='-'+sub1(s2,s1)
 else
 if s1>=s2 then sub:=sub1(s1,s2)
 else sub:='-'+sub1(s2,s1);
end;
Bài 2. Ghép số lớn ( inc(i);dec(j);
 end;
until i>j;
Qsort(l,j);Qsort(i,h);
end;
{=================}
begin
s[0]:='0'; n:=0;
while s[n]'' do
begin
 inc(n);
 readln(s[n]);
end;
qsort(1,n-1);
for i:=1 to n-1 do write(s[i]);
readln;
end.
Bài 3. Tìm số (Đề thi học sinh giỏi tỉnh lớp 11 tỉnh Hà Tĩnh năm học 2007-2008)
 Cho tr-íc mét x©u kÝ tù, trong ®ã cã Ýt nhÊt 5 ch÷ sè. H·y lo¹i bá mét sè kÝ tù ra khái 
x©u sao cho 5 kÝ tù cuèi cïng cßn l¹i theo ®óng thø tù ®ã t¹o thµnh sè lín nhÊt.
D÷ liÖu vµo: Cho trong tÖp Bai1.inp
KÕt qu¶: XuÊt ra mµn h×nh
Bai1.inp
KÕt qu¶
13a7b48cb7d9e68f7
89687
 * Ý tưởng:
 - Xóa các ký tự chữ cái xuất hiện trong xâu
 - Thực hiện xóa các kí tự số chỉ giữ lại 5 số để tạo thành số lớn nhất bằng cách lần 
lượt đi tìm 4 chữ số lớn nhất có trong xâu còn lại.
 * Chương trình tham khảo:
var f,g:text;
 s:string;
{=====================}
procedure Nhap;
Begin
 assign(f,'DL.INP'); reset(f);
 read(f,S);
 close(f);
end;
{======================}
procedure xuly;
var i,j,k:byte; For i:=1 to p do readln(a[i]);
 for i:=1 to p do readln(s[i]);
 for i:=1 to p do
 For j:=1 to A[i] do
 st:=st+S[i];
End;
{===============}
Procedure xuly;
var m:longint; sm:ansistring; code:integer;
 Begin
 j:=0;
 m:=length(st)-k;
 Repeat
 sm:='9';
 dec(m);
 For i:=j+1 to length(st)-m do
 If sm>st[i] then
 Begin
 sm:=st[i];
 j:=i;
 End;
 kq:=kq+sm;
 Until m=0;
 Val(kq,m,code);
 Write(m);
 End;
{===============}
BEGIN
 nhap;
 xuly;
 Readln
END.
2. Dạng 2. Biến đổi xâu
 Phương pháp chung: Đây là dạng cơ bản thường gặp, việc biến đổi xâu được thực 
hiện trên mỗi ký tự trong xâu nên cần nắm rõ các hàm, thủ tục trên kiểu dữ liệu xâu để vân 
dụng một cách linh hoạt vào từng bài tập cụ thể.
Bài 1. Rút gọn xâu (Đề thi HSG lớp 12 tỉnh Nghệ An năm 2009-2010)
Cho một xâu S chỉ gồm các chữ cái in thường với độ dài tối đa 250 ký tự. Em hãy viết 
chương trình để tạo ra xâu SG từ xâu S bằng cách xóa các ký tự liên tiếp giống nhau trong 
xâu S và chỉ để lại một kí tự đại diện trong đoạn đó.
Dữ liệu vào: Đọc từ file văn bản XAUGON.INP chứa xâu S chỉ gồm các chữ cái in thường.
Kết quả: Ghi ra file văn bản XAUGON.OUT là xâu SG tìm được.
Ví dụ:
XAUGON.INP
XAUGON.OUT
hhooocccsssiiiiinnnhhh aaabb
 * Ý tưởng: Với việc nén xâu ta lần lượt đi đếm các ký tự giống nhau liên tiếp trong xâu 
và sử dụng một xâu kq để lưu kết quả tìm được cho đến khi xét hết xâu (việc giải nén được 
thực hiện ngược lại)
 * Chương trình tham khảo
const fi='string.inp';
 fo='string.out';
var f,g:text; s1,s2:string;
{================}
procedure doc;
begin
 assign(f,fi); reset(f);
 readln(f,s1);
 readln(f,s2);
 close(f);
end;
{================}
procedure nen;
var s,kq:string; i,d:integer; ch:char;
begin
 d:=1; s1:=s1+#32;ch:=s1[1]; kq:='';
 for i:=2 to length(s1) do
 if s1[i]=s1[i-1] then inc(d)
 else
 begin
 str(d,s);
 if d1 then kq:=kq+s+ch else kq:=kq+ch;
 d:=1;
 ch:=s1[i];
 end;
 writeln(g,kq);
end;
{================}
procedure giainen;
var s,kq,so:string; i,j,code,n:integer; ch:char;
begin
 i:=1; kq:='';
 repeat
 so:='0';
 while s2[i] in ['1'..'9'] do begin so:=so+s2[i];inc(i); end;
 val(so,n,code);
 if n>1 then
 for j:=1 to n do kq:=kq+s2[i] end;
 end;
 writeln('so luong ki tu khac nhau:',dem);
 writeln('ky tu xuat hien nhieu lan nhat la ',kt,' so lan xh ',max);
end;
{=========}
begin
 nhap;
 xuly;
 readln;
end.
Bài 4. Gửi thư (nguồn 
 Vị Giám đốc công ty XYZ cần gửi một văn bản quan trọng tới một đối tác của mình. 
Văn bản là một xâu S các chữ cái la tinh in thường. Để bảo mật nội dung văn bản, ông 
Giám đốc gửi 2 bức thư. Bức thư thứ nhất là phần đầu Sb của xâu S, bức thư thứ 2 là phần 
cuối Se của S. Hai bức thư Sb và Se đảm bảo đầy đủ nội dung của S, tuy nhiên có thể một 
phần cuối của Sb có thể được viết lặp lại trong phần đầu của Se, song số kí tự được viết lặp 
lại không biết trước.
Ví dụ: với văn bản S=’truongnguyenduquannhat’ tạo ra hai bức thư:
Sb=’truongnguyendu’ và Se=’nguyenduquannhat’
Yêu cầu: Cho hai xâu Sb và Se, hãy xác định một xâu S có thể là nội dung của bức thư sao 
cho độ dài của xâu S là ngắn nhất.
Dữ liệu
Dòng đầu chứa xâu Sb, dòng thứ hai chứa xâu Se. Mỗi xâu có độ dài không quá 250.
Kết quả
Ghi ra độ dài của xâu S tìm được.
Ví dụ
Dữ liệu
truongnguyendu
nguyenduquannhat
Kết quả
22
 * Ý tưởng:
 - Lần lượt xét các xâu con d, c tương ứng tính từ cuối xâu s1 và đầu xâu s2, nếu d=c 
thì ta lưu lại độ dài của xâu d. Quá trình cứ tiếp tục và ta nhận được độ dài xâu con chung 
dài nhất cần tìm (giả sử là max).
 - Kết quả bài toán là length(s1)+length(s2) - max
 * Chương trình tham khảo:
var s,s1,d,c:string;
 i,kq,n,h,k,max:integer;
begin
 readln(s); read(s1);
 i:=1; h:=length(s);
 k:=length(s1); n:=min(h,k); max:=0;
 while i<=n do
 begin
 d:=copy(s,h-i+1,h);