Hướng dẫn cách đếm số lần xuất hiện của chuỗi con trong C++. Trong lập trình, việc đếm số lần xuất hiện của chuỗi con trong một chuỗi lớn là một nhiệm vụ quan trọng và thực hiện thường xuyên. Trong bài viết này, chúng ta sẽ khám phá cách thực hiện nhiệm vụ này bằng ngôn ngữ lập trình C++. Đồng thời, chúng ta cũng sẽ xem xét các ứng dụng thực tế của việc đếm số lần xuất hiện của chuỗi con trong chuỗi lớn.
Đếm Số Lần Xuất Hiện của Chuỗi Con sử Dụng Vòng Lặp và Hàm find()
Một cách đơn giản để đếm số lần xuất hiện của chuỗi con là sử dụng vòng lặp và hàm find(). Hàm find() cho phép chúng ta tìm vị trí xuất hiện đầu tiên của chuỗi con trong chuỗi lớn, và sau đó có thể di chuyển vị trí tìm kiếm để tìm các xuất hiện tiếp theo. Dưới đây là một ví dụ minh họa:
while (foundPos != string::npos) { // Tăng biến đếm khi tìm thấy chuỗi con count++;
// Di chuyển vị trí tìm kiếm sang phần sau của chuỗi lớn foundPos = mainString.find(substring, foundPos + 1); }
return count; }
intmain(){ string mainString = "This is an example string. This string contains an example."; string substring = "example";
// Gọi hàm đếm số lần xuất hiện của chuỗi con int occurrences = countSubstringOccurrences(mainString, substring);
cout << "So lan xuat hien cua chuoi con '" << substring << "' trong chuoi lon la: " << occurrences << endl;
return0; }
Trong ví dụ này, find() được sử dụng để tìm vị trí đầu tiên của chuỗi con trong chuỗi lớn. Vòng lặp while sau đó được sử dụng để tiếp tục tìm kiếm cho đến khi không còn chuỗi con nào được tìm thấy.
Sử Dụng Thuật Toán KMP (Knuth-Morris-Pratt) để Tìm Kiếm Chuỗi Con
Ngoài cách truyền thống, có các thuật toán tìm kiếm chuỗi nâng cao như thuật toán KMP (Knuth-Morris-Pratt), giúp tối ưu hóa hiệu suất tìm kiếm. Thuật toán KMP sử dụng một bảng lợi ích để giảm số lần so sánh khi tìm kiếm chuỗi con. Dưới đây là một ví dụ về cách sử dụng thuật toán KMP:
voidcomputeLPSArray(conststring &pattern, vector<int> &lps){ int len = 0; // Chiều dài của tiền tố dài nhất thỏa mãn lps[0] = 0; // LPS của ký tự đầu tiên luôn là 0
int i = 1; while (i < pattern.length()) { if (pattern[i] == pattern[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } }
intcountSubstringOccurrencesKMP(conststring &mainString, conststring &substring){ int count = 0; int mainLength = mainString.length(); int subLength = substring.length();
int i = 0; // Chỉ số của mainString int j = 0; // Chỉ số của substring
while (i < mainLength) { if (substring[j] == mainString[i]) { j++; i++; }
if (j == subLength) { // Tăng biến đếm khi tìm thấy chuỗi con count++; j = lps[j - 1]; } elseif (i < mainLength && substring[j] != mainString[i]) { if (j != 0) { j = lps[j - 1]; } else { i++; } } }
return count; }
intmain(){ string mainString = "This is an example string. This string contains an example."; string substring = "example";
// Gọi hàm đếm số lần xuất hiện của chuỗi con sử dụng thuật toán KMP int occurrences = countSubstringOccurrencesKMP(mainString, substring);
cout << "So lan xuat hien cua chuoi con '" << substring << "' trong chuoi lon la: " << occurrences << endl;
return0; }
Trong ví dụ này, hàm computeLPSArray() được sử dụng để tính toán mảng LPS (Longest Proper Prefix which is also Suffix) cho chuỗi con. Hàm countSubstringOccurrencesKMP() sau đó sử dụng thuật toán KMP để đếm số lần xuất hiện của chuỗi con trong chuỗi lớn.
Ứng Dụng Trong Thực Tế
Phân Tích Văn Bản và Dữ Liệu
Trong xử lý ngôn ngữ tự nhiên và phân tích dữ liệu văn bản, việc đếm số lần xuất hiện của các cụm từ hoặc thuật ngữ cụ thể có thể giúp hiểu rõ hơn về nội dung và xu hướng.
#include<iostream> #include<string>
usingnamespacestd;
voidanalyzeText(conststring &text, conststring &term){ // Gọi hàm đếm số lần xuất hiện của chuỗi con int occurrences = countSubstringOccurrences(text, term);
cout << "So lan xuat hien cua chuoi con '" << term << "' trong van ban la: " << occurrences << endl;
// Tiếp tục phân tích dữ liệu văn bản... }
intmain(){ string text = "Natural language processing is a subfield of artificial intelligence."; string term = "language";
// Gọi hàm phân tích văn bản analyzeText(text, term);
return0; }
Kiểm Soát Dữ Liệu Người Dùng
Trong ứng dụng sử dụng dữ liệu người dùng, việc kiểm tra sự xuất hiện của chuỗi con có thể giúp đảm bảo tính hợp lệ của thông tin nhập vào.
// Kiểm tra sự xuất hiện của chuỗi con cấm if (countSubstringOccurrences(password, forbiddenTerm) > 0) { cout << "Mat khau khong hop le. Vui long chon mat khau khac." << endl; returnfalse; }
// Tiếp tục kiểm tra tính hợp lệ khác của mật khẩu... returntrue; }
intmain(){ string userPassword;
cout << "Nhap mat khau: "; getline(cin, userPassword);
// Gọi hàm kiểm tra tính hợp lệ của mật khẩu if (validatePassword(userPassword)) { cout << "Mat khau hop le. Tien hanh dang nhap..." << endl; }
return0; }
Tổng Kết
Trên đây Kiyoshi đã hướng dẫn bạn về cách đếm số lần xuất hiện của chuỗi con trong C++ rồi. Việc đếm số lần xuất hiện của chuỗi con trong một chuỗi lớn không chỉ giúp phân tích dữ liệu mà còn mang lại nhiều ứng dụng thực tế. Bằng cách sử dụng các kỹ thuật lập trình và thuật toán tìm kiếm phù hợp, chúng ta có thể linh hoạt và hiệu quả trong việc giải quyết vấn đề này. Từ phân tích văn bản đến kiểm soát dữ liệu người dùng, khả năng đếm số lần xuất hiện của chuỗi con trong chuỗi lớn giúp nâng cao chất lượng và tính ứng dụng của các ứng dụng lập trình.