c++程序设计速学4字符串处理

字符串操作

字符串初始化和赋值：使用构造函数或赋值运算符初始化和赋值字符串。
字符串连接：使用 + 运算符或 += 运算符连接字符串。
字符串长度：使用 length() 或 size() 方法获取字符串的长度。
字符串查找：使用 find 方法查找子字符串的位置，返回 std::string::npos 表示未找到。
字符串替换：使用 replace 方法替换字符串的一部分。
字符串分割：使用 std::istringstream 和 std::getline 方法将字符串按分隔符分割成多个子字符串。
字符串转换：使用 std::transform 方法将字符串转换为大写或小写。
字符串比较：使用 ==、!=、<、<=、>、>= 运算符比较字符串。

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <cctype>int main() {// 1. 字符串初始化和赋值std::string str1 = "Hello";std::string str2 = "World";std::string str3 = str1; // 复制赋值str3 = "C++"; // 直接赋值std::cout << "str1: " << str1 << std::endl;std::cout << "str2: " << str2 << std::endl;std::cout << "str3: " << str3 << std::endl;// 2. 字符串连接std::string str4 = str1 + " " + str2;std::cout << "str4: " << str4 << std::endl;// 3. 字符串长度size_t length = str4.length();std::cout << "Length of str4: " << length << std::endl;// 4. 字符串查找size_t pos = str4.find("World");if (pos != std::string::npos) {std::cout << "Found 'World' at position: " << pos << std::endl;} else {std::cout << "'World' not found" << std::endl;}// 5. 字符串替换str4.replace(pos, 5, "C++");std::cout << "After replacement: " << str4 << std::endl;// 6. 字符串分割std::string str5 = "apple,banana,orange";std::istringstream iss(str5);std::vector<std::string> tokens;std::string token;while (std::getline(iss, token, ',')) {tokens.push_back(token);}std::cout << "Tokens: ";for (const auto& t : tokens) {std::cout << t << " ";}std::cout << std::endl;// 7. 字符串转换// to uppercasestd::transform(str4.begin(), str4.end(), str4.begin(), ::toupper);std::cout << "Uppercase: " << str4 << std::endl;// to lowercasestd::transform(str4.begin(), str4.end(), str4.begin(), ::tolower);std::cout << "Lowercase: " << str4 << std::endl;// 8. 字符串比较std::string str6 = "hello c++";if (str4 == str6) {std::cout << "str4 and str6 are equal" << std::endl;} else {std::cout << "str4 and str6 are not equal" << std::endl;}return 0;
}

子字符串提取：使用 substr 方法提取子字符串。

std::string subStr = str4.substr(0, 5); // 提取从索引 0 开始的 5 个字符
std::cout << "Substring: " << subStr << std::endl;

字符串拼接：使用 std::stringstream 拼接多个字符串.

std::stringstream ss;
ss << "Hello, " << "World!";
std::string result = ss.str();
std::cout << "Result: " << result << std::endl;

去除字符串首尾空白：自定义函数去除字符串首尾的空白字符。

std::string trim(const std::string& str) {size_t first = str.find_first_not_of(' ');if (std::string::npos == first) {return str;}size_t last = str.find_last_not_of(' ');return str.substr(first, (last - first + 1));
}std::string str7 = "   Hello World!   ";
std::string trimmedStr = trim(str7);
std::cout << "Trimmed: " << trimmedStr << std::endl;

暴力匹配算法（Brute Force）

暴力匹配算法是最简单的模式匹配算法，从文本的第一个字符开始，逐个字符与模式进行比较。
如果匹配失败，移动到下一个字符继续比较。

#include <iostream>
#include <string>int bruteForceSearch(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();for (int i = 0; i <= n - m; ++i) {int j;for (j = 0; j < m; ++j) {if (text[i + j] != pattern[j]) {break;}}if (j == m) {return i; // 模式匹配成功，返回起始位置}}return -1; // 模式匹配失败
}int main() {std::string text = "ABACADABRAC";std::string pattern = "ABRA";int pos = bruteForceSearch(text, pattern);if (pos != -1) {std::cout << "Pattern found at index: " << pos << std::endl;} else {std::cout << "Pattern not found" << std::endl;}return 0;
}

KMP 算法（Knuth-Morris-Pratt）

KMP 算法通过预处理模式来避免不必要的比较，从而提高效率。
计算模式的前缀函数（部分匹配表）。
利用前缀函数在匹配失败时快速跳过已经比较过的字符。

#include <iostream>
#include <string>
#include <vector>std::vector<int> computeLPSArray(const std::string& pattern) {int m = pattern.length();std::vector<int> lps(m, 0);int len = 0;int i = 1;while (i < m) {if (pattern[i] == pattern[len]) {len++;lps[i] = len;i++;} else {if (len != 0) {len = lps[len - 1];} else {lps[i] = 0;i++;}}}return lps;
}int kmpSearch(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();std::vector<int> lps = computeLPSArray(pattern);int i = 0; // 文本的索引int j = 0; // 模式的索引while (i < n) {if (pattern[j] == text[i]) {i++;j++;}if (j == m) {return i - j; // 模式匹配成功，返回起始位置} else if (i < n && pattern[j] != text[i]) {if (j != 0) {j = lps[j - 1];} else {i++;}}}return -1; // 模式匹配失败
}int main() {std::string text = "ABACADABRAC";std::string pattern = "ABRA";int pos = kmpSearch(text, pattern);if (pos != -1) {std::cout << "Pattern found at index: " << pos << std::endl;} else {std::cout << "Pattern not found" << std::endl;}return 0;
}

Boyer-Moore 算法

Boyer-Moore 算法通过跳过不可能匹配的部分来提高效率。
使用坏字符规则和好后缀规则来决定跳过的步长。
坏字符规则：根据模式中最后一个字符在模式中的位置决定跳过的步长。
好后缀规则：根据模式的后缀在模式中的位置决定跳过的步长。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>std::vector<int> badCharHeuristic(const std::string& pattern, int alphabetSize) {std::vector<int> badChar(alphabetSize, -1);for (int i = 0; i < pattern.length(); ++i) {badChar[pattern[i]] = i;}return badChar;
}int boyerMooreSearch(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();int alphabetSize = 256; // ASCII 字符集大小std::vector<int> badChar = badCharHeuristic(pattern, alphabetSize);int s = 0; // 模式在文本中的起始位置while (s <= (n - m)) {int j = m - 1;while (j >= 0 && pattern[j] == text[s + j]) {j--;}if (j < 0) {return s; // 模式匹配成功，返回起始位置} else {s += std::max(1, j - badChar[text[s + j]]);}}return -1; // 模式匹配失败
}int main() {std::string text = "ABACADABRAC";std::string pattern = "ABRA";int pos = boyerMooreSearch(text, pattern);if (pos != -1) {std::cout << "Pattern found at index: " << pos << std::endl;} else {std::cout << "Pattern not found" << std::endl;}return 0;
}

Rabin-Karp 算法

Rabin-Karp 算法使用哈希函数来快速查找模式。
计算模式的哈希值。
计算文本中每个子串的哈希值，并与模式的哈希值进行比较。
如果哈希值相同，再进行逐字符比较以确认是否真正匹配。

#include <iostream>
#include <string>const int d = 256; // 字符集大小
const int q = 101; // 一个大素数，用于取模int rabinKarpSearch(const std::string& text, const std::string& pattern) {int n = text.length();int m = pattern.length();int h = 1;int p = 0; // 模式的哈希值int t = 0; // 当前文本子串的哈希值for (int i = 0; i < m - 1; ++i) {h = (h * d) % q;}for (int i = 0; i < m; ++i) {p = (d * p + pattern[i]) % q;t = (d * t + text[i]) % q;}for (int i = 0; i <= n - m; ++i) {if (p == t) {int j;for (j = 0; j < m; ++j) {if (text[i + j] != pattern[j]) {break;}}if (j == m) {return i; // 模式匹配成功，返回起始位置}}if (i < n - m) {t = (d * (t - text[i] * h) + text[i + m]) % q;if (t < 0) {t = t + q;}}}return -1; // 模式匹配失败
}int main() {std::string text = "ABACADABRAC";std::string pattern = "ABRA";int pos = rabinKarpSearch(text, pattern);if (pos != -1) {std::cout << "Pattern found at index: " << pos << std::endl;} else {std::cout << "Pattern not found" << std::endl;}return 0;
}