SKKN Một số biện pháp ôn tập có hiệu quả phần kiểu dữ liệu xâu nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi môn Tin học

c trên xâu giáo viên cần lấy ví dụ cụ thể mô phỏng cho học sinh hiểu rõ bản chất. Giáo viên có thể bổ sung thêm một số bài tập vận dụng nhỏ, mức độ trung bình có sử dụng các hàm và thủ tục chuẩn xử lí xâu để học sinh củng cố chắc kiến thức vừa học.
Kết quả sau khi thực hiện giải pháp 1: Học sinh nắm được các thao tác trên xâu kí tự, vận dụng được để giải được các bài tập trong sách giáo khoa là tiền đề vững chắc để các em học các buổi nâng cao sau.
2.3.2 Giải pháp 2: Phân loại các dạng toán điển hình trên xâu kí tự.
2.3.2.1.Dạng 1: Dạng toán cơ bản. 
Phương pháp chung: Đây là dạng cơ bản thường gặp, những bài toán cơ bản như: Đưa xâu về dạng chuẩn, đếm số kí tự nào đó xuất hiện trong xâu hay đếm số từ trong xâu... Các bài toán ở dạng này tương đối dễ hiểu với học sinh.
Bài toán 1.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
hocsinh
* Ý tưởng: 
Duyệt từ đầu xâu đến cuối xâu, gặp 2 kí tự liên tiếp giống nhau thì xóa đi 1kí tự.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 1.2Chữ cái xuất hiện(Đề thi HSG tỉnh Thanh Hóa năm 2012)
Cho xâu St chỉ gồm các chữ cái. Tính số lần xuất hiện của chữ cái xuất hiện nhiều nhất trong xâu (không phân biệt chữ in hoa và in thường).
Dữ liệu vào:Từ file KT_MAX.INP gồm: Xâu St (độ dài ≤ 500 kí tự).
Kết quả:Ghi ra file KT_MAX.OUT gồm: Một dòng duy nhất là bội số chung nhỏ nhất của kết quả bài toán và 105.
Ví dụ:
KT_MAX.INP
KT_MAX.OUT
AAABDA
100000
*Ý tưởng:
Dùng mảng D để lưu số lần xuất hiện của mỗi phần tử trong xâu st sau đó ta chỉ việc duyệt từ đầu đến cuối mảng D để tìm phần tử lớn nhất của mảng là max. Kết quả bài toán chính bội chung nhỏ nhất của max và 10000.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 1.3 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 vào từ file GUITHU.INP:
- 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.
Dữ liệu ra đưa ra file GUITHU.OUT:Ghi ra độ dài của xâu S tìm được.
Ví dụ:
GUITHU.INP
GUITHU.OUT
truongnguyendu
nguyenduquannhat
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 như vậy 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: (Mô tả chi tiết ở phụ lục).
2.3.2.2. Dạng 2: Xóa và thay thế.
Phương pháp chung: Để giải các bài toán của dạng 2ta thực hiện lặp đi lặp lại (câu lệnh lặp while) các công việc: Tìm vị trí, xóa và thay thế.
Bài toán 2.1 Giải mã (Đề thi HSG lớp 12 tỉnh Vĩnh Phúc năm 2012 – 2013)
	Cho xâu s đã được mã hóa theo quy tắc các nguyên âm a, e, i, o, u được viết thêm chữ cái p đằng sau và thêm chính nguyên âm đó đằng sau chữ cái p. Đưa ra xâu sau khi giải mã
Ví dụ:Từ ‘welcome’ sẽ được mã hóa thành ‘wepelcopomepe’
* Ý tưởng: 
Sử dụng ý tưởng chung của dạng bài tập này là tìm vị trí xuất hiện, xóa đi hai kí tự từ vị trí tìm được +1. Bình thường vị trí xuất hiện của xâu x trong xâu s chỉ có 1 nhưng ở đây có 5 trường hợp. Vì vậy, sử dụng mảng để duyệt từng trường hợp.
* Đoạn chương trình:
x[1]:= ‘apa’; x[2]:= ‘epe’; x[3]:= ‘ipi’; x[4]:= ‘opo’; x[5]:= ‘upu’; 
for i:=1 to 5 do
while pos(x[i], s) 0 do 
begin
vt:= pos(x[i], s); delete(s,vt+1, 2);
end;
Bài toán 2.2 Xóa số(Đề HSG lớp 10tỉnh Vĩnh Phúc năm 2011 – 2012)
Cho số nguyên dương gồm N chữ số, tìm số lớn nhất có thể sau khi gạch bỏ đi k chữ số trong số N chữ số đã cho.
Ví dụ: với N=3; k=1 số đó là 991 số còn lại sau khi xóa là 99 Với N=4; k=2 số đó là 1782 số còn lại sau khi xóa là 82.
* Ý tưởng:
	- Đọc số vào dưới dạng xâuS.
	- Duyệt từ đầu xâu, xét 2 kí tựliền kề nhau nếu s[i]<s[i+1] thì xóa s[i], giảm k đi 1 đơn vị. Công việc này thực hiện lặp đi lặp lại cho đến khi k=0 hoặc duyệt hết xâuS.
	- Nếu sau khi duyệt ở trên mà k>0 thì xâu S còn lại là xâu gồm các kí tự số theo thứ tự giảm dần, như vậy chỉ cần xóa từ cuối xâu đúng k kí tự.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 2.3 Tìm số lớn (Đề thi HSG tỉnh Thanh Hóa 2013 - 2014)
Cho một dãy gồm N các kí tự có mặt trên bàn phím trong đó có ít nhất 4 chữ số (N< 106).
Yêu cầu: Hãy loại bỏ một số kí tự khỏi dãy sao cho 4 kí tự cuối cùng còn lại theo đúng thứ tự đó tạo nên 1 số lớn nhất.
Dữ liệu vào: File văn bản chứa MAX.INP chứa N kí tự.
Dữ liệu ra: File văn bản MAX.OUT chứa 4 chữ số tạo thành số lớn nhất.
Ví dụ:
MAX.INP
MAX.OUT
24t5j4r05f704y652k393
7693
* Ý tưởng: 
- Lọc ra xâu S chỉ chứa các kí tự số
- Áp dụng phương pháp giải của bài toán 2.2 với k = n-4
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
2.3.2.3. Dạng 3: Các bài tập xâu Palindrome.
Phương pháp chung: Xâu Palindrome hay còn gọi là xâu đối xứng. Xâu đối xứng là xâu có tính chất: Đọc nó từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải.
Với những bài tập kiểm tra xâu Palindrome hay tìm kiếm xâu có tính chất Palindrome thì trước hết nên xây dựng hàm kiểm tra tính chất đối xứng của một xâu với độ phức tạp O(n), trên cơ sở đó chúng ta đi giải quyết những bài tập khó hơn.
Bài toán 3.1 Khóa vòng(Nguồn https://www.ddth.com/showthread.php)
Người ta xâu N viên đá kích thước giống nhau thành 1 vòng đeo cổ (5<=N<=250), mỗi viên có 1 màu trong số các màu đánh số từ 1 đến 9. Người ta định lắp khóa đeo vào vị trí sao cho khi mở vòng ta được một dây đá có tính chất: Không phụ thuộc vào việc cầm đầu dây nào bên tay phải và đầu kia bên tay trái, ta đều được một chuỗi hạt giống nhau, tức là viên đá thứ i từ trái sang luôn có màu j không phụ thuộc vào cách cầm.
Dữ liệu:Đọc từ file KHOAVONG.INP gồm xâu S chứa các kí tự từ 0..9 có độ dài bé hơn 256.
Kết quả:Ghi ra file KHOAVONG.OUT số cách đặt khóa khác nhau thỏa mãn yêu cầu. 
Ví dụ: 
KHOAVONG.INP
KHOAVONG.OUT
222222335533
2
* Ý tưởng:
Xử lí dữ liệu vòng tròn bằng cách nhân đôi xâu ban đầu, kiểm tra từng xâu con có độ dài bằng N bắt đầu từ vị trí i (i = 1, 2,..., N) có là xâu đối xứng không? Nếu đối xứng thì tăng biến đếm.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán3.2 Robot công nghiệp
(Đề thi HSG lớp 11 tỉnh Hà Tĩnh năm học 2010-2011)
Trong một nhà máy có trang bị loại Robot công nghiệp để thực hiện việc tự động hoá gia công các sản phẩm. Việc gia công các sản phẩm của Robot được thực hiện đồng thời trên hai sản phẩm cùng một lúc theo tiến trình: Với mỗi loại thao tác gia công được Robot thực hiện trên sản phẩm thứ nhất xong rồi chuyển sang thực hiện trên sản phẩm thứ hai. Để hoàn thành một sản phẩm, Robot có thể thực hiện tới N loại thao tác gia công (N≤ 24) và mỗi loại thao tác gia công đã thực hiện trên một sản phẩm nào đó rồi thì không thực hiện lại trên sản phẩm đó nữa. Robot hoạt động bằng lệnh là một dãy kí tự in hoa, mỗi kí tự là lệnh thực hiện cho một loại thao tác gia công. Lệnh thực hiện các loại thao tác gia công khác nhau là các kí tự khác nhau. Việc đọc dòng lệnh và thực hiện lệnh của Robot được tiến hành theo các chu trình như sau:
+ Chu trình thứ nhất: Đọc kí tự thứ nhất, thực hiện lệnh tương ứng trên sản phẩm thứ nhất. Tiếp theo đọc kí tự thứ N, thực hiện lệnh tương ứng trên sản phẩm thứ hai.
+ Chu trình thứ hai: Đọc kí tự thứ hai, thực hiện lệnh tương ứng trên sản phẩm thứ nhất. Tiếp theo đọc kí tự thứ N-1, thực hiện lệnh tương ứng trên sản phẩm thứ hai.
+ Chu trình thứ ba: Đọc kí tự ba, thực hiện lệnh tương ứng trên sản phẩm thứ nhất. Tiếp theo đọc kí tự thứ N-2, thực hiện lệnh tương ứng trên sản phẩm thứ hai.
 ...
Tương tự với các chu trình còn lại để đọc hết dòng lệnh.
Với một xâu S các kí tự in hoa có số lượng các kí tự là chẵn và không quá N x 2, hãy xác định xem nó có phải là một dòng lệnh của Robot đã nói ở trên hay không?
Dữ liệu vào: Tệp văn bản ROBOT.INP có cấu trúc:
- Dòng đầu tiên ghi 1 số là độ dài xâu S.
- Dòng thứ 2 ghi xâu S.
Dữ liệu ra: Tệp văn bản ROBOT.OUT ghi thông báo ‘CO’ nếu xâu S là dòng lệnh của Robot, ngược lại ghi thông báo ‘KHONG’
Ví dụ:
ROBOT.INP
ROBOT.OUT
6
CO
CBAABC
ROBOT.INP
ROBOT.OUT
6
KHONG
ACBDCA
* Ý tưởng: 
Với yêu cầu của đề bài, bài toán trở thành kiểm tra xâu đầu vào có đối xứng hay không. Nếu xâu đầu vào đối xứng thì ghi ra tệp dữ liệu ra “CO”, ngược lại thì ghi “KHONG”.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 3.3 Đối xứng kép (Đề thi HSG lớp 12 tỉnh Vĩnh Phúc năm 2011)
Với mỗi xâu T, ta kí hiệu Trlà xâu nhận được từ T bằng cách viết T theo chiều từ phải qua trái, chẳng hạn (abc)r= cba. Mỗi xâu đối xứng độ dài chẵn luôn có dạng T.Tr, dấu ‘.’để chỉ phép nối xâu. 
Ta định nghĩa một xâu là đối xứng kép nếu nó có dạng TTrTTr, chẳng hạn abbaabbalà một xâu đối xứng kép với T= ab. 
Cho xâu S, xác định độ dài xâu con đối xứng kép dài nhất của S. 
Dữ liệu: Cho bởi file dpalin.inp ghi xâu S với độ dài không vượt quá 1000,chỉ gồm các chữ cái latinh từ a..z, A..Z. 
Kết quả: Ghi ra file dpalin.out trên một dòng gồm một số nguyên là độ dài xâu con đối xứng kép dài nhất của xâu S. 
Ví dụ:
dpalin.inp
dpalin.out
Aaaaxyyxxyyxbbbb
8
	* Ý tưởng: 
	Dùng mảng S để lưu xâu đã cho. Dùng thêm mảng hai chiều d kích thước 1000x1000 kiểu boolean để kiểm tra có thỏa mãn dpalin hay không tại mỗi điểm xétd:array[1..10000,1..10000]of boolean;
Gọi n là độ dài xâu S, gọi max là độ dài xâu con đối xứng kép dài nhất.
Ta duyệt từ đầu xâu đến độ dài trừ 2.
for i:=1 to n-2 do
begin
if S[i]=S[i+1] then
begin
d[i,i+1]:=true;
j:=i-1;k:=i+2;
while (j>=1)and(k<=n)and(S[j] = S[k]) do
begin
d[j,k]:=true;
dec(j);inc(k);
end;
end;
end;
for i:=1 to n do
for j:=i+2 to n do
if d[i,j] then
begin
k:=(i+j) div 2;
if d[i,k] then if j-i+1>max then max:=j-i+1;
	end;
Kết quả bài toán là max.
2.3.2.4. Dạng 4: Mã hóa và giải mã.
Phương pháp chung: 
-	Sử dụng mảng gán giá trị ban đầu cho các kí tự từ A đến Z là 1 đến 26.
-	Theo yêu cầu đề bài phải xây dựng được hàm f.
-	Từ hàm f giải mã ngược trở lại theo quy tắc mã hóa.
Bài toán 4.1 Mã hóa (Đề thi HSG tỉnh Vĩnh Phúc 2008 -2009)
Một người thích làm một việc như sau: Anh ta xem các chữ cái tiếng Anh từ A đến Z là các số tương ứng từ 1 đến 26. Khi đó thay vì viết một từ tiếng Anh, anh ta viết dãy số nhận được bằng cách thay mỗi chữ cái xuất hiện trong đó bằng số tương ứng, dãy số này được gọi là mã hóa của từ đó. Nhập từ bàn phím một dãy chữ số thập phân S1 gồm không quá 30 chữ số. Hãy in ra mọi từ S mà S1 là mã hóa của nó. Nếu không có thì in ra -1.
Ví dụ:
MAHOA.INP
MAHOA.OUT
123
ABC
AW
LC
* Ý tưởng:
	Đọc dãy chữ số thập phân S1 vào xâu St. Dùng mảng A gồm tối đa 30 kí tự để lưu các kí tự sẽ được mã hóa. Độ dài xâu số St là N. 
	Dùng biến OK có kiểu boolean để kiểm tra xem việc mã hóa có thành công hay không. Nếu OK = true thì việc mã hóa thành công và kết quả của mã hóa là mảng A còn nếu Ok = false thì việc mã hóa không thành công và kết quả của mã hóa là -1.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 4.2Từ điển (Nguồn từ diễn đàn lập trình CTS.edu.vn)
Hai từ được gọi là ANAGRAM của nhau nếu từ này là một hoán vị các kí tự của từ kia và ngược lại, chẳng hạn DARE và READ là ANAGRAM của nhau. 
Yêu cầu: Hãy tìm các nhóm từ là ANAGRAM của nhau.
Dữ liệu:Vào từ File văn bản TUDIEN.INP gồm N từ không có dấu, chỉ toàn chữ cái thường (1< N<=100), mỗi từ được ghi trên một dòng 
Kết quả: Ghi ra File văn bản TUDIEN.INP có cấu trúc: Mỗi nhóm từ là ANAGRAM của nhau được ghi trên một dòng, mỗi từ cách nhau một dấu cách trống.
Ví dụ: 
TUDIEN.INP
TUDIEN.OUT
Care
read
race
opt
dear
dare
care race
dear dare read
opt
* Ý tưởng:
Dùng mảng A tối đa 100 phần tử, mỗi phần tử là một xâu để đọc dữ liệu: Mỗi từ trên một dòng được lưu vào một phần tử của mảng A. Dùng thêm mảng B có cấu trúc hoàn toàn như A để lấy phần tử từ A trong quá trình xử lí. Đầu tiên ta sắp xếp lại mảng B (chính là nội dung của mảng A) sau đó kiểm tra có phải là anagram không
for i:= 1 to n do
begin
B[i]:= A[i];
for j:= 1 to length(B[i])-1 do
for k:= j+1 to length(B[i]) do
if B[i][j]>B[i][k] then
begin
ch:= B[i][j];
B[i][j]:= B[i][k];
B[i][k]:= ch;
end;
end;
for i:= 1 to n-1 do
for j:= i+1 to n do
if B[i]>B[j] then
begin
S:= b[i]; B[i]:=B[j]; B[j]:=S;
S:= a[i]; a[i]:=a[j]; a[j]:=S;
end;
for i:= 1 to n do
if B[i]=B[i+1] then write(f,A[i],' ')
else writeln(f,A[i]);
Bài toán 4.3Xâu hạt nhân (Nguồn từ HBCCoder – Bài tập)
Xâu u được gọi là hạt nhân của xâu v nếu u là xâu ngắn nhất sao cho ghép một số lần u thì nhận được v. Cho xâu S, tìm hạt nhân của nó.
Dữ liệu: Cho từ file XAU_HN.INP gồm một xâu S.
Kết quả: Ghi ra file XAU_HN.OUT là hạt nhân của xâu S.
Ví dụ:
XAU_HN.INP
XAU_HN.OUT
Abcabcabc
Abc
* Ý tưởng:
Dùng biến S để lưu trữ xâu đã cho, trước tiên ta dùng hàm KT để kiểm tra xâu u có thỏa mãn xâu hạt nhân hay không?
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
2.3.2.5. Dạng 5: Tìm xâu con.
Phương pháp chung: Để tìm các xâu con (tức là một xâu con gồm các kí tự liên tiếp nhau)thỏa mãn một điều kiện cho trước thì thường sử dụng phương pháp vét cạn với bộ dữ liệu đầu vào nhỏ, tuy nhiên nên sử dụng linh hoạt các phương pháp khác như phương pháp quy hoạch động, phương pháp chặt nhị phân trong trường hợp bài toán có bộ dữ liệu lớn.
Bài toán 5.1. Xâu chung(Đề thi HSG tỉnh Nghệ An lớp 12 năm 2013)
	Xâu S được gọi là xâu con chung của xâu S1 và xâu S2 nếu xâu S là một dãy các kí tự liên tiếp trong S1 và cũng là dãy các kí tự liên tiếp trong S2. 
Yêu cầu: Cho hai xâu kí tự S1 và S2 (có không quá 255 kí tự). Hãy tìm một xâu con chung S dài nhất của hai xâu S1 và S2. 
Ví dụ: S1 = ‘Ky thi học sinh gioi Tinh mon Tin hoc’, S2 = ‘hoc sinh gioi mon Tin hoc’ thì S = ‘hoc sinh gioi’.
Dữ liệu:Vào từ file văn bản xauchung.inp:
Dòng đầu tiên ghi xâu S1.
Dòng thứ hai ghi xâu S2.
Kết quả:Ghi ra file văn bảnxauchung.out chỉ một số duy nhất là độ dài của xâu con chung dài nhất S. (Nếu hai xâu S1, S2 không có kí tự nào chung thì ghi số 0).
Ví dụ: 
xauchung.inp
xauchung.out
Ky thi hoc sinh gioi Tinh mon tin hoc
hoc sinh gioi mon Tin hoc
14
* Ý tưởng:
Trước tiên ta xây dựng thủ tục để cập nhật độ dài xâu con chung lớn nhất tại các thời điểm:
procedure capnhat;
begin
if kmax < k then kmax:=k;
end;
Quá trình tìm xâu con chung lớn nhất hoàn toàn tương tự như phương pháp đoạn xâu lớn nhất: 
procedure xuly;
begin
l1:=length(s1);
l2:=length(s2);
	k:=0;
kmax:=0;
for i:=1 to l1 do
	for j:=1 to l2 do
	if s1[i]=s2[j] then
	begin
	k:=1;
	while (i+k<=l1) and (j+k<=l2) and (s1[i+k]=s2[j+k]) do
inc(k);
	capnhat;
	end;
end;
Kết quả của bài toán là kmax.
Bài toán 5.2Đoạn max(Đề thi HSG tỉnh Nghệ An lớp 12 năm 2014)
	Cho chuỗi kí tự S gồm toàn các chữ cái in hoa (‘A’’Z’) với độ dài không quá 104. 
Yêu cầu:Hãy tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đầu tiên trong chuỗi S.
Dữ liệu: Vào từ văn bản DOANMAX.INP: Gồm một dòng duy nhất chứa chuỗi S.
Kết quả: Ghi ra file văn bảnDOANMAX.OUT
Chỉ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiều dài của đoạn con dài nhất tìm được.
Ví dụ: 
DOANMAX.INP
DOANMAX.OUT
ABABCDAC
3 4
Lưu ý: Có 80% số test có độ dài xâu S không vượt quá 255.
Giải thích test ví dụ: Đoạn con dài nhất tìm được là ABCD có vị trí 3 và độ dài 4.
* Ý tưởng:
“Cách 1: Một cách đơn giản nhất là ta duyệt trực tiếp từ đầu xâu đến cuối xâu tất cả các cặp i và j. Với mỗi cặp duyệt để kiểm tra từng cặp.
Với cách làm này độ phức tạp lên đến O(N4)
Cách 2: Ta nâng cấp cách 1 trên bằng một số nhận xét:
Vì xâu chỉ chứa các kí tự từ A đến Z (bao gồm 26 kí tự) nên độ dài đoạn con dài nhất thỏa mãn yêu cầu sẽ không quá 26.
- Xét mọi đoạn con có độ dài d và cận đầu là i:
+ Vì cần tìm đoạn con dài nhất nên ta xét độ dài d giảm dần từ 26 về 1 và dãy đầu tiên thỏa mãn là dãy dài nhất cần tìm.
+ Với mỗi d cần xét tất cả các dãy con có độ dài d, các dãy con đó có cận đầu nhận giá trị từ 1 đến n- d +1
- Với mỗi đoạn con cận đầu i và độ dài d(tức là từ 1 đến n- d +1) ta kiểm tra xem trong đoạn đó có 2 kí tự giống nhau hay không.
Với cách làm này độ phức tạp đã giảm xuống còn O(263 N) 
Cách 3: Ta nâng cấp thuật toán đạt mức chuẩn nhất:
- Gọi cd là vị trí bắt đầu của đoạn cần tìm
- Gọi B là mảng có chỉ số là các kí tự từ A đến Z
Khai báo B: array [‘A’..’Z’] of longint;
Với B[c] = j tức là j là vị trí của kí tự c được cập nhật mới nhất.
Với mỗi kí tự S[i] ta có:
+ Nếu B[s[i]] >= cd vị trí mới của cd là B[s[i]]+ 1
	+ Khi đó các kí tự từ vị trí cd đến vị trí i sẽ đôi một khác nhau, so sánh độ dài và lưu lại.
+ Cập nhật lại vị trí của S[i] là B[s[i]]:= i. 
Với cách làm này độ phức tạp đã giảm xuống đạt chuẩn thấp nhất
O(N)”. [2]
Chương trình tham khảo ở cách 3: (Mô tả chi tiết ở phụ lục).
Bài toán 5.3Chiếc nón kỳ diệu 
(Đề thi HSG lớp 12 tỉnh Phú Yên năm học 2009-2010)
Một lần trong chương trình “Chiếc nón diệu kỳ”, ở phần chơi dành cho khán giả, thay vì đoán chữ như mọi khi, người dẫn chương trình tự mình quay “chiếc nón” và cho hiện lên màn hình trước mặt khán giả trong trường quay các số trong các ô mà kim chỉ thị lần lượt đi qua. “Chiếc nón” quay đúng một số nguyên vòng, nên trong dãy số hiện lên màn hình, số cuối cùng trùng với số đầu tiên. Sau đó, người dẫn chương trình mời một khán giả ở cuối trường quay (chỉ nhìn thấy màn hình mà không nhìn thấy “chiếc nón”) cho biết chiếc nón có tối thiểu bao nhiêu ô?
Yêu cầu: Hãy trả lời câu hỏi của người dẫn chương trình.
Dữ liệu: Vào từ tập tin văn bản CNDK.INP gồm hai dòng:
+ Dòng 1 ghi số N là số lượng số đã hiện lên màn hình (2 <= N<= 100).
+ Dòng 2 ghi lần lượt N số, mỗi số có giá trị không quá 32000.
Kết quả: Ghi ra tập tin văn bản CNDK.OUT số ô tối thiểu của “chiếc nón”.
Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.
Ví dụ:
CNDK.INP
CNDK.OUT
13
5 3 1 3 5 2 5 3 1 3 5 2 5
6
* Ý tưởng:
Nhận thấy nếu ghép toàn bộ các số hiện lên màn hình (trừ số cuối cùng) vào một xâu S thì trong xâu S sẽ luôn tồn tại một xâu s1 dài nhất mà khi ghép liên tiếp một số lần xâu s1 ta sẽ được xâu s. Số lần xuất hiện xâu s1 là kết quả cần tìm. Bài toán trở thành tìm xâu con dài nhất s1.
Chương trình tham khảo: (Mô tả chi tiết ở phụ lục).
Bài toán 5.4 Xâu Palindrome
(Đề thi HSG tỉnh Thanh Hóa 2012-2013)
	Một xâu kí tự được gọi là xâu Palindrome (đối xứng) nếu ta đọc từ trái sang phải hay đọc từ phải sang trái đều giống nhau.
Yêu cầu: Cho trước một xâu kí tự S. Hãy xác định số xâu đối xứng là xâu con của nó. Một kí tự cũng được coi là một xâu đối xứng. Xâu con của S là xâu gồm một số kí tự liên tiếp trong S.
Dữ liệu vào: Từ tệp văn bản Palindrom.INP:
- Dòng thứ nhất ghi số nguyên dương N (N<100).
- N dòng tiếp theo mỗi dòng là một xâu kí tự (độ dài xâu <255).
Kết quả: Ghi vào tệp văn bản Palindrom.OUT gồm:
- N dòng, mỗi dòng chứa một số nguyên biểu thị số x