Sáng kiến kinh nghiệm Phương pháp giải một số bài toán chuổi con bằng ngôn ngữ lập trình C++

 2 
 SỞ GIÁO DỤC & ĐÀO TẠO NGHỆ AN 
 TRƢỜNG THPT KIM LIÊN 
 SÁNG KIẾN KINH NGHIỆM 
Đề tài: 
 “PHƢƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN CHUỔI 
 CON BẰNG NNLT C++” 
 Lĩnh vực: Tin học 
 Giáo viên: Nguyễn Quang Hùng – Nguyễn Thị Lƣu 
 Trƣờng THPT Kim Liên 
 Năm học: 2022-2023 
 Số điện thoại: 0973484114 - 0914527656 
 2 
 PHẦN I. ĐẶT VẤN ĐỀ 
1. Lý do chọn đề tài 
 Chúng ta đang từng bước triển khai Chương trình giáo dục phổ thông mới, 
trong đó môn Tin học ngày càng khẳng định vai trò chủ đạo trong việc trang bị cho 
người học khả năng tìm kiếm, tiếp nhận, mở rộng tri thức và sáng tạo trong thời 
đại cách mạng công nghiệp lần thứ tư và toàn cầu hóa. 
 Trong quá trình giảng dạy chúng tôi đã dành nhiều thời gian để tìm kiếm, 
sưu tầm, phân loại được một số bài tập về xử lý chuổi con. Nên chúng tôi cùng 
nghiên cứu và viết đề tài “PHƢƠNG PHÁP GIẢI MỘT SỐ BÀI TOÁN 
CHUỔI CON BẰNG NNLT C++” nhằm hệ thống hóa toàn bộ kiến thức về dữ 
liệu kiểu chuổi để giúp giáo viên và học sinh sử dụng trong việc dạy và học. 
 Khi trao đổi với đồng nghiệp cùng trường và một số giáo viên ở trường 
khác trong khu vực, chúng tôi nhận thấy còn nhiều giáo viên khi dạy về vấn đề xử 
lý chuổi con còn khó khăn khi đưa ra các bài tập và code viết bằng NNLT C++, 
cho nên chúng tôi mạnh dạn trao đổi kinh nghiệm của mình. Rất mong các đồng 
nghiệp nhận xét, góp ý để đề tài của chúng tôi ngày càng hoàn thiện và ứng dụng 
rộng rãi trong thực tiễn. 
Các bài toán và code mà chúng tôi đưa ra chỉ nhằm giới thiệu cho học sinh cách 
viết chứ chưa hẳn là một phương án tối ưu để giải quyết bài toán cụ thể đó. 
 2. Tính cấp thiết của đề tài 
 Các bài toán xử lý chuổi con là rất quan trọng trong lập trình, nó thường gây 
ra khó khăn cho học sinh khi mới bắt đầu làm quen và Giáo viên khi mới bắt đầu 
viết C++. Vì vậy việc đưa ra nhiều bài toán và code của nó là rất cần thiết. 
3. Tính mới của đề tài 
- Đưa ra được nhiều bài tập mới về chuổi con và code viết bằng NNLT C++ 
- Đưa ra một số định hướng để giải bài toán về xử lý chuổi con trong NNLT C++ 
4. Khả năng ứng dụng và triển khai đề tài 
 Đề tài có thể là tài liệu tham khảo bổ ích cho Học sinh, Giáo viên THPT đặc 
biệt là Học sinh khá, giỏi. 
5. Đối tƣợng và phạm vi nghiên cứu 
5.1. Đối tƣợng nghiên cứu 
- Học sinh THPT. 
- Giáo viên trường THPT. 
 4 
thỏa mãn điều kiện Q thì thì mọi xâu con liên tục của A cũng thoả mãn điều kiện 
Q và ta cũng chỉ tính một xâu con là A. 
 Dạng 3: Cho xâu ký tự S. Yêu cầu: Tìm xâu con dài nhất của S thỏa mãn 
điều kiện Q. 
 Trường hợp 1: Điều kiện Q có tính chất: Xâu con A thỏa mãn điều kiện Q 
nhưng các xâu con của A có thể không thỏa mãn Q. 
 Trường hợp 2: Điều kiện Q có tính chất: Nếu xâu con A thỏa mãn điều kiện 
Q thì mọi xâu con liên tục của A cũng thoả mãn tính chất Q và các ký tự của A 
không được xét vào xâu con khác. 
1.2. Cơ sơ thực tiễn 
 Chúng tôi đã tìm tòi các bài toán về chuổi con, nghiên cứu kỹ các code và 
đúc rút ra một số kinh nghiệm cho bản thân trong quá trình dạy học. 
2. Thực trạng 
 Các bài toán về xử lý chuổi con là các bài toán cơ bản. Nhưng trong thực tế 
vấn đề dạy và học về kiểu chuổi bằng NNLT C++, Giáo viên và Học sinh còn gặp 
một số khó khăn và hạn chế 
 6 
Dạng 1: Bài toán duyệt theo phƣơng pháp vét cạn. 
1.1/ Bài toán: 
 Cho chuỗi kí tự S. Hãy tìm ra tất cả các chuổi con của S thoả mãn điều kiện 
Q. 
1.2/ Phân tích: 
 Với bài toán này, đề yêu cầu đưa ra tất cả các chuỗi con (các chuỗi con có 
thể lồng nhau, có thể giao nhau) nên phải kiểm tra tất cả các chuỗi con. Để kiểm 
tra hết ta phải duyệt theo phương pháp vét cạn. 
1.3/ Ý tưởng thuật toán: 
 Để giải quyết bài toán này trong C++, ta có thể sử dụng phương pháp vét 
cạn, tức là kiểm tra tất cả các chuỗi con của S có thỏa mãn điều kiện Q hay không. 
Cụ thể, ta sẽ duyệt qua tất cả các vị trí i, j (i ≤ j) trong chuỗi S và lấy ra chuỗi con 
từ vị trí i đến j. Sau đó, kiểm tra xem chuỗi con này có thỏa mãn điều kiện Q hay 
không. Nếu có, ta lưu lại đoạn ký tự tìm được và tiếp tục duyệt đến vị trí tiếp theo. 
Để kiểm tra chuỗi con có thỏa mãn điều kiện Q hay không, ta cần định nghĩa điều 
kiện đó. Ví dụ, nếu điều kiện là chuỗi con có chứa chữ số, ta có thể duyệt qua từng 
ký tự trong chuỗi con và kiểm tra xem ký tự đó có phải là số hay không. Nếu có ít 
nhất một ký tự là số, ta coi chuỗi con này thỏa mãn điều kiện Q. 
Sau khi duyệt qua tất cả các vị trí trong chuỗi S, ta sẽ có được tất cả các đoạn ký tự 
thỏa mãn điều kiện Q. Ta in ra các đoạn này và kết thúc chương trình. 
Dưới đây là code về cách giải bài toán này trong C++ 
 #include 
 #include 
 using namespace std; 
 int main() 
 { 
 string s; 
 getline(cin, s); // nhập xâu ký tự 
 for (int i = 0; i < s.length(); i++) 
 8 
 3 4 
 4 4 
 5 5 
 5 6 
 6 6 
 Ý tưởng: 
Để giải quyết bài toán này bằng phương pháp vét cạn, chúng ta có thể thực hiện 
các bước sau: 
 1. Đọc chuỗi ký tự S từ tệp đầu vào. 
 2. Duyệt qua tất cả các xâu con của chuỗi S. Với mỗi xâu con, kiểm tra xem 
 các ký tự trong xâu con đều giống nhau hay không. 
 3. Nếu xâu con đồng nhất, ghi lại vị trí đầu và cuối của xâu con vào tệp đầu ra. 
 4. Kết thúc quá trình duyệt và đóng tệp đầu vào và tệp đầu ra. 
Dƣới đây là đoạn code minh họa cho bài toán này: 
 #include 
#include 
#include 
using namespace std; 
bool checkSame(string s, int start, int end) { 
 // Hàm kiểm tra xâu con từ vị trí start đến vị trí end có đồng nhất không 
 for(int i = start + 1; i <= end; i++) { 
 if(s[i] != s[start]) { 
 return false; 
 } 
 } 
 return true; 
 10 
 } 
 } 
 inFile.close(); 
 outFile.close(); 
 return 0; 
} 
Dạng 2: Bài toán duyệt theo phƣơng pháp phát triển chuổi con. 
2.1/ Bài toán: 
 Cho chuổi S. Hãy đưa ra các đoạn ký tự là chuổi con của S thỏa mãn điều 
kiện Q nào đó. Trong đó điều kiện Q có tính chất: Nếu chuổi con A thỏa mãn điều 
kiện Q thì mọi chuổi con liên tục của A cũng thoả mãn tính chất Q và lúc đó ta 
cũng chỉ tính một chuổi con là A. 
2.2/ Phân tích: 
 Với dạng này yêu cầu chuổi con thoả mãn Q có các tính chất trên nên ta sẽ 
duyệt theo phương pháp Phát triển chuổi con (kiểm tra sự thỏa mãn của phần tử 
tiếp theo để bổ sung vào đoạn đã tìm được). 
2.3/ Ý tưởng thuật toán: 
 Đầu tiên, ta khởi tạo một chuỗi rỗng, sau đó duyệt qua từng ký tự của chuỗi 
S. Tại mỗi bước lặp, ta thêm ký tự đó vào cuối chuỗi rỗng để tạo thành một chuỗi 
con mới. Sau đó, ta kiểm tra xem chuỗi con mới này có thỏa mãn điều kiện Q hay 
không. Nếu thỏa mãn, ta lưu trữ chuỗi con này vào một danh sách các chuỗi con 
thỏa mãn Q. 
Sau khi duyệt qua toàn bộ chuỗi S, ta sẽ có danh sách các chuỗi con của chuỗi S 
thỏa mãn điều kiện Q. 
Ví dụ, nếu điều kiện Q là "chuỗi con chứa ít nhất một ký tự 'a'", 
Code minh họa nhƣ sau 
#include 
#include 
#include 
using namespace std; 
 12 
 Cho tệp văn bản DONG_NHAT_2.INP gồm 1 dòng chứa xâu ký tự S với độ 
dài không quá 250 ký tự. Hãy cắt xâu S thành các xâu con đồng nhất, sao cho số 
xâu con là ít nhất. Kết quả ghi vào tệp DONG_NHAT_2.Out mỗi dòng là 1 xâu 
con đồng nhất. 
 Dong_nhat_2.Inp Dong_nhat_2.OUT 
 hooocc h 
 ooo 
 cc 
Ý tưởng: 
Đầu tiên, ta duyệt qua từng ký tự của chuỗi S. Tại mỗi bước lặp, ta kiểm tra xem 
ký tự hiện tại có giống với ký tự trước đó hay không. Nếu giống nhau, ta thêm ký 
tự đó vào chuỗi con hiện tại. Nếu khác nhau, ta lưu trữ chuỗi con hiện tại vào danh 
sách các chuỗi con đồng nhất và khởi tạo chuỗi con mới bắt đầu từ ký tự hiện tại. 
Sau khi duyệt qua toàn bộ chuỗi S, ta sẽ có danh sách các chuỗi con đồng nhất của 
chuỗi S. 
Code bài toán: 
 #include 
 #include 
 #include 
 #include 
 using namespace std; 
 int main() 
 { 
 ifstream infile("DONG_NHAT_2.INP"); 
 ofstream outfile("DONG_NHAT_2.OUT"); 
 string s; 
 getline(infile, s); 
 vector substrings; 
 14 
Dạng 3: Bài toán tìm xâu con dài nhất. 
3.1/ Bài toán: 
 Cho chuỗi ký tự S. Tìm ra chuỗi con dài nhất thoả mãn một tính chất Q nào 
đó. 
3.2/ Phân tích: 
 Bài toán trên có thể giải quyết bằng một số phương pháp như: 
 1. Vét cạn: Kiểm tra tất cả các chuỗi con của chuỗi S và kiểm tra tính chất Q 
 của từng chuỗi con. Lưu lại độ dài của chuỗi con thoả mãn tính chất Q và trả 
 về chuỗi con dài nhất. 
 2. Sử dụng thuật toán Quy hoạch động: Dùng một mảng dp để lưu độ dài của 
 chuỗi con dài nhất thoả mãn tính chất Q tại mỗi vị trí trong chuỗi S. Từ đó, 
 ta có thể tính toán độ dài của chuỗi con dài nhất thoả mãn tính chất Q tại vị 
 trí cuối cùng của chuỗi S. 
 3. Sử dụng phương pháp phát triển chuổi con. 
3.3/ Ý tưởng giải bài toán trên bằng phương pháp phát triển chuổi con 
 1. Tạo ra tất cả các chuỗi con có thể từ chuỗi S. 
 2. Kiểm tra tính chất Q của từng chuỗi con. 
 3. Lưu lại độ dài của chuỗi con thoả mãn tính chất Q và trả về chuỗi con dài 
 nhất. 
 Ta có thể cài đặt đoạn code nhƣ sau: 
 #include 
 #include 
 using namespace std; 
 // Hàm kiểm tra tính chất Q của một chuỗi con 
 bool check(string str) { 
 // Code kiểm tra tính chất Q của chuỗi con ở đây 
 } 
 // Hàm tìm chuỗi con dài nhất thoả mãn tính chất Q 
 string longestSubstring(string s) { 
 16 
chuỗi S. Nếu có nhiều chuỗi con thỏa mãn thì đưa ra dãy đầu tiên tính từ trái sang 
phải. 
 Kết quả ghi vào tệp Dong_nhat_3.OUT gồm 1 dòng là chuỗi con tìm được. 
 Ví dụ: 
 Dong_nhat_3.Inp Dong_nhat_3.OUT 
 hooocc ooo 
 Ý tưởng: 
 Duyệt từ đầu đến cuối chuỗi S và lưu trữ số lượng ký tự đồng nhất liên tiếp 
 tại mỗi vị trí. Ví dụ, nếu chuỗi S là "abbbccdd", ta sẽ có mảng count = {1, 3, 
 2, 2, 1, 1, 1, 1}. 
 Duyệt qua mảng count và tìm phần tử lớn nhất. Lưu lại vị trí của phần tử lớn 
 nhất đó. 
 Sử dụng vị trí lớn nhất đã tìm được và độ dài phần tử lớn nhất đó để trích 
 xuất chuỗi con đồng nhất có độ dài lớn nhất từ chuỗi S. 
Code của bài toán: 
#include 
#include 
using namespace std; 
int main() { 
 string S; 
 cin >> S; 
 int n = S.length(); 
 int count[n]; 
 for (int i = 0; i < n; i++) { 
 int j = i + 1; 
 while (j < n && S[j] == S[i]) j++; 
 count[i] = j - i; 
 } 
 int max_len = 0, max_pos = 0; 
 for (int i = 0; i < n; i++) { 
 if (count[i] > max_len) { 
 18 
#include 
using namespace std; 
int main() { 
 ifstream fin("XAUGON.INP"); 
 ofstream fout("XAUGON.OUT"); 
 string S, SG; 
 fin >> S; 
 char prev_char = '\0'; 
 for (char c : S) { 
 if (c != prev_char) { 
 SG += c; 
 prev_char = c; 
 } 
 } 
 fout << SG << endl; 
 fin.close(); 
 fout.close(); 
 return 0; 
} 
Bài 2: NÉN XÂU (Đề thi HSG tỉnh lớp 12 năm học 2011 – 2012) 
 Một xâu ký tự có thể nén lại bằng 1 xâu mới bằng cách nén các ký tự giống 
nhau đứng cạnh nhau. Ví dụ trong xâu AAAA sẽ nén thành 4A. Hãy lập trình để 
nén 1 xâu ký tự in hoa theo cách trên. 
 20 
 if (count == 1) { 
 compressedStr += currentChar; 
 } else { 
 compressedStr += to_string(count) + currentChar; 
 } 
 currentChar = inputStr[i]; 
 count = 1; 
 } 
 } 
 if (count == 1) { 
 compressedStr += currentChar; 
 } else { 
 compressedStr += to_string(count) + currentChar; 
 } 
 outFile << compressedStr; 
 inFile.close(); 
 outFile.close(); 
 return 0; 
} 
Bài 3. XÂU CON CHUNG DÀI NHẤT 
(Đề thi HSG tỉnh lớp 12 năm học 2012 – 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 
môn 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 Bai2.inp: 
 22 
 // Xây dựng ma trận dp 
 for (int i = 1; i <= m; i++) { 
 for (int j = 1; j <= n; j++) { 
 if (s1[i-1] == s2[j-1]) { 
 dp[i][j] = dp[i-1][j-1] + 1; 
 } else { 
 dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
 } 
 } 
 } 
 return dp[m][n]; 
} 
int main() { 
 string s1, s2; 
 getline(cin, s1); // Nhập xâu S1 
 getline(cin, s2); // Nhập xâu S2 
 int res = LCS(s1, s2); 
 cout << res << endl; // Xuất kết quả 
 return 0; 
} 
Bài 6. XÂU CON (Đề thi HSG tỉnh lớp 11 năm học 2014 – 2015) 
 Cho trước một xâu có độ dài L (1 < L < 2.105) chỉ chứa các chữ cái thường 
trong bảng chữ cái tiếng Anh. 
 Yêu cầu: 
 Hãy tìm xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu đã cho. 
 Dữ liệu vào từ file XAU.INP: 
 24 
 return pi; 
} 
int main() { 
 ifstream input("XAU.INP"); 
 ofstream output("XAU.OUT"); 
 int n; 
 string s; 
 input >> n >> s; 
 vector pi = prefixFunction(s); 
 int result = 0; 
 for (int i = 1; i < n; i++) { 
 if (pi[i] > 0 && pi[i] < i && pi[i] == pi[pi[i]-1]) { 
 result = max(result, pi[i]); 
 } 
 } 
 output << result << endl; 
 return 0; 
} 
3.5. Một số bài tập mở rộng: 
Bài 1: 
 Trong lập trình khái niệm từ được hiểu là một dãy ký tự không chứa dấu 
cách. Cho tệp văn bản XAU.INP chứa 1 xâu ký tự trong đó có cả chữ cái và chữ 
số. Hãy viết chương trình xử lý các yêu cầu sau: 
 a/ Tách xâu chưa chuẩn hoá thành mỗi từ 1 dòng. 
 b/ Loại bỏ các dấu cách thừa trong xâu để giữa các từ chỉ còn 1 dấu cách. 
 c/ Đưa ra từ dài nhất trong xâu. 
 d/ Đưa ra xâu con tạo thành số nguyên lớn nhất. 
 Các kết quả ghi vào tệp văn bản lần lượt là A.OUT, B.OUT, C.OUT, 
 D.OUT, E.OUT. 
Gợi ý: 
 a/ Xác định các chuỗi con không chứa các dấu cách và ghi chúng trên 1 
dòng. Nên duyệt phương pháp phát triển chuỗi con.