Dưới đây là tổng hợp về kỹ thuật xử lý chuỗi và các thuật toán nâng cao trong C++ giúp bạn làm việc hiệu quả hơn với các bài toán phức tạp liên quan đến chuỗi:
Kỹ thuật xử lý chuỗi trong C++
Các thao tác cơ bản với std::string
Khởi tạo:
std::string s1 = "Hello";
std::string s2("World");
Nối chuỗi:
std::string s3 = s1 + " " + s2;
Trích xuất ký tự:
char c = s1[0]; // 'H'
Cắt chuỗi (substr):
std::string sub = s3.substr(6, 5); // "World"
Xử lý nâng cao với stringstream
Tách chuỗi dựa trên dấu phân cách:
#include <sstream>
#include <vector>
std::vector<std::string> split(const std::string &s, char delimiter) {
std::vector<std::string> tokens;
std::string token;
std::stringstream ss(s);
while (std::getline(ss, token, delimiter)) {
tokens.push_back(token);
}
return tokens;
}
Kỹ thuật sử dụng regex
Kiểm tra chuỗi có khớp với biểu thức chính quy:
#include <regex>
bool isValidEmail(const std::string &email) {
std::regex pattern(R"((\w+)(\.?\w*)@(\w+)(\.\w+))");
return std::regex_match(email, pattern);
}
Thuật toán nâng cao xử lý chuỗi
KMP (Knuth-Morris-Pratt) – Tìm kiếm mẫu trong chuỗi
#include <vector>
#include <iostream>
std::vector<int> computeLPS(const std::string &pattern) {
int m = pattern.size();
std::vector<int> lps(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = lps[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
lps[i] = j;
}
return lps;
}
void KMP(const std::string &text, const std::string &pattern) {
int n = text.size();
int m = pattern.size();
std::vector<int> lps = computeLPS(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = lps[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
std::cout << "Found pattern at index: " << i - m + 1 << std::endl;
j = lps[j - 1];
}
}
}
int main() {
std::string text = "ababcabcabababd";
std::string pattern = "ababd";
KMP(text, pattern);
return 0;
}
Z-Algorithm – Tìm kiếm chuỗi con
#include <vector>
#include <iostream>
std::vector<int> computeZ(const std::string &s) {
int n = s.size();
std::vector<int> z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) {
z[i] = std::min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
std::string text = "ababcababc";
std::string pattern = "abc";
std::string combined = pattern + "$" + text;
auto z = computeZ(combined);
for (int i = pattern.size() + 1; i < z.size(); i++) {
if (z[i] == pattern.size()) {
std::cout << "Pattern found at index: " << i - pattern.size() - 1 << std::endl;
}
}
return 0;
}
Thuật toán Rabin-Karp
Sử dụng giá trị băm để tìm chuỗi con:
#include <iostream>
#include <string>
#include <cmath>
const int PRIME = 101;
int hashValue(const std::string &s, int length) {
int hash = 0;
for (int i = 0; i < length; i++) {
hash += s[i] * std::pow(PRIME, i);
}
return hash;
}
void RabinKarp(const std::string &text, const std::string &pattern) {
int n = text.size();
int m = pattern.size();
int patternHash = hashValue(pattern, m);
int textHash = hashValue(text, m);
for (int i = 0; i <= n - m; i++) {
if (patternHash == textHash) {
if (text.substr(i, m) == pattern) {
std::cout << "Pattern found at index " << i << std::endl;
}
}
if (i < n - m) {
textHash = (textHash - text[i]) / PRIME + text[i + m] * std::pow(PRIME, m - 1);
}
}
}
int main() {
std::string text = "abcdeabc";
std::string pattern = "abc";
RabinKarp(text, pattern);
return 0;
}
Các bài tập cơ bản về xâu ký tự
Bài 1: Đảo ngược chuỗi
Đề bài: Nhập vào một chuỗi bất kỳ. In ra chuỗi đảo ngược của chuỗi đó.
Gợi ý:
- Sử dụng vòng lặp từ cuối chuỗi về đầu.
- Hoặc sử dụng hàm
reverse()từ thư viện<algorithm>.
#include <iostream>
#include <algorithm>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::reverse(s.begin(), s.end());
std::cout << "Chuoi dao nguoc: " << s << std::endl;
return 0;
}
Bài 2: Đếm số lần xuất hiện của một ký tự
Đề bài: Nhập một chuỗi và một ký tự từ bàn phím. Đếm số lần ký tự đó xuất hiện trong chuỗi.
Gợi ý:
Dùng vòng lặp for và so sánh từng ký tự trong chuỗi.
#include <iostream>
#include <string>
int main() {
std::string s;
char x;
int count = 0;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::cout << "Nhap ky tu can dem: ";
std::cin >> x;
for (char c : s) {
if (c == x) count++;
}
std::cout << "So lan xuat hien cua ky tu '" << x << "' la: " << count << std::endl;
return 0;
}
Bài 3: Kiểm tra chuỗi đối xứng (Palindrome)
Đề bài: Nhập một chuỗi và kiểm tra xem chuỗi đó có đối xứng hay không.
Gợi ý:
So sánh ký tự từ đầu và cuối dần vào giữa chuỗi.
#include <iostream>
#include <string>
bool isPalindrome(const std::string &s) {
int n = s.size();
for (int i = 0; i < n / 2; i++) {
if (s[i] != s[n - i - 1]) {
return false;
}
}
return true;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
if (isPalindrome(s)) {
std::cout << "Chuoi doi xung!" << std::endl;
} else {
std::cout << "Chuoi khong doi xung!" << std::endl;
}
return 0;
}
Bài 4: Tách từ trong chuỗi
Đề bài: Nhập một chuỗi và in ra từng từ trong chuỗi.
Gợi ý:
Dùng stringstream từ thư viện <sstream>.
#include <iostream>
#include <sstream>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::stringstream ss(s);
std::string word;
std::cout << "Cac tu trong chuoi: " << std::endl;
while (ss >> word) {
std::cout << word << std::endl;
}
return 0;
}
Bài 5: Đếm số từ trong chuỗi
Đề bài: Nhập một chuỗi và đếm số từ trong chuỗi.
Gợi ý:
Tận dụng bài tách từ ở trên.
#include <iostream>
#include <sstream>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::stringstream ss(s);
std::string word;
int count = 0;
while (ss >> word) {
count++;
}
std::cout << "So tu trong chuoi: " << count << std::endl;
return 0;
}
Bài 6: Xóa khoảng trắng thừa trong chuỗi
Đề bài: Nhập một chuỗi và xóa hết khoảng trắng thừa giữa các từ (bao gồm cả đầu và cuối chuỗi).
Gợi ý:
Sử dụng stringstream kết hợp với kiểm tra thủ công.
#include <iostream>
#include <sstream>
#include <string>
std::string removeExtraSpaces(const std::string &s) {
std::stringstream ss(s);
std::string word, result;
while (ss >> word) {
if (!result.empty()) {
result += " ";
}
result += word;
}
return result;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::cout << "Chuoi sau khi xoa khoang trang thua: "
<< removeExtraSpaces(s) << std::endl;
return 0;
}
Bài 7: Đếm số ký tự hoa, thường, số và ký tự đặc biệt
Đề bài: Nhập một chuỗi và đếm số lượng ký tự hoa, thường, số và ký tự đặc biệt trong chuỗi.
#include <iostream>
#include <string>
#include <cctype>
int main() {
std::string s;
int upper = 0, lower = 0, digit = 0, special = 0;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
for (char c : s) {
if (std::isupper(c)) upper++;
else if (std::islower(c)) lower++;
else if (std::isdigit(c)) digit++;
else special++;
}
std::cout << "So ky tu hoa: " << upper << std::endl;
std::cout << "So ky tu thuong: " << lower << std::endl;
std::cout << "So chu so: " << digit << std::endl;
std::cout << "So ky tu dac biet: " << special << std::endl;
return 0;
}
Các bài tập nâng cao về xâu ký tự
Bài 1: Kiểm tra chuỗi con xuất hiện nhiều nhất
Đề bài: Nhập một chuỗi và tìm chuỗi con có độ dài bất kỳ xuất hiện nhiều lần nhất.
Gợi ý:
Lưu chuỗi con vào map để đếm số lần xuất hiện.
Sử dụng hàm substr() để trích xuất các chuỗi con.
#include <iostream>
#include <map>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::map<std::string, int> substringCount;
int maxCount = 0;
std::string mostFrequentSubstring;
for (size_t i = 0; i < s.size(); i++) {
for (size_t len = 1; len <= s.size() - i; len++) {
std::string sub = s.substr(i, len);
substringCount[sub]++;
if (substringCount[sub] > maxCount) {
maxCount = substringCount[sub];
mostFrequentSubstring = sub;
}
}
}
std::cout << "Chuoi con xuat hien nhieu nhat: " << mostFrequentSubstring
<< " (" << maxCount << " lan)" << std::endl;
return 0;
}
Bài 2: Tìm chuỗi con đối xứng dài nhất (Longest Palindromic Substring)
Đề bài: Nhập một chuỗi và tìm chuỗi con đối xứng dài nhất.
Gợi ý:
Sử dụng kỹ thuật mở rộng từ giữa (Expand Around Center).
#include <iostream>
#include <string>
std::string expandFromCenter(const std::string &s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
std::string longestPalindrome(const std::string &s) {
if (s.empty()) return "";
std::string longest;
for (int i = 0; i < s.size(); i++) {
std::string odd = expandFromCenter(s, i, i); // Palindrome có độ dài lẻ
std::string even = expandFromCenter(s, i, i + 1); // Palindrome có độ dài chẵn
if (odd.size() > longest.size()) longest = odd;
if (even.size() > longest.size()) longest = even;
}
return longest;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::cout << "Chuoi con doi xung dai nhat: " << longestPalindrome(s) << std::endl;
return 0;
}
Bài 3: Xóa tất cả ký tự trùng nhau trong chuỗi
Đề bài: Nhập một chuỗi và xóa tất cả các ký tự xuất hiện nhiều hơn 1 lần.
Gợi ý:
Sử dụng unordered_map để đếm tần suất xuất hiện.
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::unordered_map<char, int> frequency;
for (char c : s) {
frequency[c]++;
}
std::string result;
for (char c : s) {
if (frequency[c] == 1) {
result += c;
}
}
std::cout << "Chuoi sau khi xoa ky tu trung: " << result << std::endl;
return 0;
}
Bài 4: Mã hóa chuỗi theo quy tắc Run-Length Encoding (RLE)
Đề bài: Nhập một chuỗi và mã hóa theo quy tắc Run-Length Encoding (RLE).
Gợi ý:
RLE nén chuỗi theo dạng số lần xuất hiện + ký tự. Ví dụ: "aaabbc" → "3a2b1c".
#include <iostream>
#include <string>
std::string runLengthEncode(const std::string &s) {
if (s.empty()) return "";
std::string encoded;
int count = 1;
for (size_t i = 1; i <= s.size(); i++) {
if (i < s.size() && s[i] == s[i - 1]) {
count++;
} else {
encoded += std::to_string(count) + s[i - 1];
count = 1;
}
}
return encoded;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::cout << "Chuoi ma hoa RLE: " << runLengthEncode(s) << std::endl;
return 0;
}
Bài 5: Kiểm tra hai chuỗi có là hoán vị của nhau hay không
Đề bài: Nhập hai chuỗi và kiểm tra xem chúng có phải là hoán vị (permutation) của nhau hay không.
Gợi ý:
Hai chuỗi là hoán vị nếu có cùng tần suất xuất hiện của các ký tự.
#include <iostream>
#include <algorithm>
#include <string>
bool arePermutations(const std::string &s1, const std::string &s2) {
if (s1.size() != s2.size()) return false;
std::string sorted1 = s1;
std::string sorted2 = s2;
std::sort(sorted1.begin(), sorted1.end());
std::sort(sorted2.begin(), sorted2.end());
return sorted1 == sorted2;
}
int main() {
std::string s1, s2;
std::cout << "Nhap chuoi thu nhat: ";
std::getline(std::cin, s1);
std::cout << "Nhap chuoi thu hai: ";
std::getline(std::cin, s2);
if (arePermutations(s1, s2)) {
std::cout << "Hai chuoi la hoan vi cua nhau." << std::endl;
} else {
std::cout << "Hai chuoi khong phai hoan vi." << std::endl;
}
return 0;
}
Bài 6: Kiểm tra chuỗi có chứa tất cả các ký tự của bảng chữ cái tiếng Anh hay không (Pangram)
Đề bài: Nhập một chuỗi và kiểm tra xem chuỗi đó có chứa tất cả các ký tự từ 'a' đến 'z' hay không.
#include <iostream>
#include <string>
#include <cctype>
#include <unordered_set>
bool isPangram(const std::string &s) {
std::unordered_set<char> letters;
for (char c : s) {
if (std::isalpha(c)) {
letters.insert(std::tolower(c));
}
}
return letters.size() == 26;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
if (isPangram(s)) {
std::cout << "Chuoi la pangram." << std::endl;
} else {
std::cout << "Chuoi khong la pangram." << std::endl;
}
return 0;
}
Bài 7: Đếm số từ trong chuỗi
Đề bài: Nhập một chuỗi và đếm số từ có trong chuỗi (các từ được phân cách bởi khoảng trắng).
Gợi ý:
Sử dụng stringstream để tách từ trong chuỗi.
#include <iostream>
#include <sstream>
#include <string>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::stringstream ss(s);
std::string word;
int count = 0;
while (ss >> word) {
count++;
}
std::cout << "So tu trong chuoi: " << count << std::endl;
return 0;
}
Bài 8: Xóa tất cả khoảng trắng thừa trong chuỗi
Đề bài: Nhập một chuỗi và xóa tất cả khoảng trắng thừa (bao gồm khoảng trắng đầu, cuối và giữa các từ).
Gợi ý:
Dùng stringstream để xử lý chuỗi.
#include <iostream>
#include <sstream>
#include <string>
std::string removeExtraSpaces(const std::string &s) {
std::stringstream ss(s);
std::string word, result;
while (ss >> word) {
if (!result.empty()) result += " ";
result += word;
}
return result;
}
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::string cleaned = removeExtraSpaces(s);
std::cout << "Chuoi sau khi xoa khoang trang thua: \"" << cleaned << "\"" << std::endl;
return 0;
}
Bài 9: Kiểm tra chuỗi có phải chuỗi đảo ngược của chuỗi khác
Đề bài: Nhập hai chuỗi và kiểm tra xem chuỗi thứ hai có phải là đảo ngược của chuỗi thứ nhất hay không.
#include <iostream>
#include <string>
#include <algorithm>
bool isReverse(const std::string &s1, const std::string &s2) {
if (s1.size() != s2.size()) return false;
return std::equal(s1.begin(), s1.end(), s2.rbegin());
}
int main() {
std::string s1, s2;
std::cout << "Nhap chuoi thu nhat: ";
std::getline(std::cin, s1);
std::cout << "Nhap chuoi thu hai: ";
std::getline(std::cin, s2);
if (isReverse(s1, s2)) {
std::cout << "Chuoi thu hai la dao nguoc cua chuoi thu nhat." << std::endl;
} else {
std::cout << "Chuoi thu hai khong phai dao nguoc." << std::endl;
}
return 0;
}
Bài 10: Mã hóa chuỗi theo quy tắc Caesar Cipher
Đề bài: Nhập một chuỗi và một số nguyên k, mã hóa chuỗi theo quy tắc Caesar Cipher (dịch mỗi ký tự sang phải k vị trí trong bảng chữ cái).
Gợi ý:
Dùng phép modulo % để xử lý vòng lặp ký tự.
#include <iostream>
#include <string>
#include <cctype>
std::string caesarCipher(const std::string &s, int k) {
std::string result;
k = k % 26; // Giới hạn dịch chuyển
for (char c : s) {
if (std::isalpha(c)) {
char offset = std::isupper(c) ? 'A' : 'a';
result += (c - offset + k) % 26 + offset;
} else {
result += c;
}
}
return result;
}
int main() {
std::string s;
int k;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::cout << "Nhap so buoc dich chuyen: ";
std::cin >> k;
std::cout << "Chuoi sau ma hoa Caesar: " << caesarCipher(s, k) << std::endl;
return 0;
}
Bài 11: So sánh hai chuỗi bất kể khoảng trắng và viết hoa viết thường
Đề bài: Nhập hai chuỗi và kiểm tra xem chúng có giống nhau nếu bỏ qua khoảng trắng và không phân biệt chữ hoa chữ thường.
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
std::string normalize(const std::string &s) {
std::string result;
for (char c : s) {
if (!std::isspace(c)) {
result += std::tolower(c);
}
}
return result;
}
int main() {
std::string s1, s2;
std::cout << "Nhap chuoi thu nhat: ";
std::getline(std::cin, s1);
std::cout << "Nhap chuoi thu hai: ";
std::getline(std::cin, s2);
if (normalize(s1) == normalize(s2)) {
std::cout << "Hai chuoi giong nhau." << std::endl;
} else {
std::cout << "Hai chuoi khac nhau." << std::endl;
}
return 0;
}
Bài 12: Tìm ký tự xuất hiện nhiều nhất trong chuỗi
Đề bài: Nhập một chuỗi và tìm ký tự xuất hiện nhiều nhất (không phân biệt chữ hoa, chữ thường).
Gợi ý:
Sử dụng mảng đếm tần suất frequency[256].
#include <iostream>
#include <string>
#include <cctype>
#include <unordered_map>
int main() {
std::string s;
std::cout << "Nhap chuoi: ";
std::getline(std::cin, s);
std::unordered_map<char, int> frequency;
char mostFrequentChar = '\0';
int maxCount = 0;
for (char c : s) {
if (std::isalpha(c)) {
char lower = std::tolower(c);
frequency[lower]++;
if (frequency[lower] > maxCount) {
maxCount = frequency[lower];
mostFrequentChar = lower;
}
}
}
std::cout << "Ky tu xuat hien nhieu nhat: '" << mostFrequentChar << "' (" << maxCount << " lan)" << std::endl;
return 0;
}
CHÚC CÁC BẠN HỌC TỐT!
