Đếm số lần xuất hiện của chuỗi con trong C++ | Laptrinhcanban.com

HOME › >>

Đếm số lần xuất hiện của chuỗi con trong C++

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:

#include <iostream>
#include <string>

using namespace std;

int countSubstringOccurrences(const string &mainString, const string &substring) {
int count = 0;
size_t foundPos = mainString.find(substring);

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;
}

int main() {
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;

return 0;
}

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:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void computeLPSArray(const string &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++;
}
}
}
}

int countSubstringOccurrencesKMP(const string &mainString, const string &substring) {
int count = 0;
int mainLength = mainString.length();
int subLength = substring.length();

vector<int> lps(subLength, 0);
computeLPSArray(substring, lps);

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];
} else if (i < mainLength && substring[j] != mainString[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}

return count;
}

int main() {
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;

return 0;
}

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>

using namespace std;

void analyzeText(const string &text, const string &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...
}

int main() {
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);

return 0;
}

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.

#include <iostream>
#include <string>

using namespace std;

bool validatePassword(const string &password) {
string forbiddenTerm = "password";

// 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;
return false;
}

// Tiếp tục kiểm tra tính hợp lệ khác của mật khẩu...
return true;
}

int main() {
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;
}

return 0;
}

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.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/chuoi-string-trong-cpp/dem-so-lan-xuat-hien-cua-chuoi-con-trong-cpp/

Hãy chia sẻ và cùng lan tỏa kiến thức lập trình Nhật Bản tại Việt Nam!

HOME  › >>

Profile
きよしです!笑

Tác giả : Kiyoshi (Chis Thanh)

Kiyoshi là một cựu du học sinh tại Nhật Bản. Sau khi tốt nghiệp đại học Toyama năm 2017, Kiyoshi hiện đang làm BrSE tại Tokyo, Nhật Bản.