【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（一）https://developer.aliyun.com/article/1467572
4. 字符串处理方法
4.1 字符串匹配
字符串匹配是指在一个文本串中查找一个模式串的过程。常用的字符串匹配算法有暴力匹配、KMP算法、Boyer-Moore算法等。
4.1.1 暴力匹配
暴力匹配算法，也称为朴素匹配算法，是最简单直观的字符串匹配算法。它的原理是从文本串的每个位置开始，逐个字符与模式串进行比较，直到找到匹配或者遍历完整个文本串。
// 暴力匹配算法示例代码 int bruteForce(string text, 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; // 匹配失败，返回-1 }
暴力匹配算法的时间复杂度为O(n * m)，其中n为文本串的长度，m为模式串的长度。
4.1.2 KMP算法
KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，它利用模式串的特点，在匹配过程中避免不必要的回溯。
// KMP算法示例代码 void getNext(string pattern, int next[]) { int m = pattern.length(); next[0] = -1; int i = 0, j = -1; while (i < m - 1) { if (j == -1 || pattern[i] == pattern[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } int kmp(string text, string pattern) { int n = text.length(); int m = pattern.length(); int* next = new int[m]; getNext(pattern, next); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || text[i] == pattern[j]) { i++; j++; } else { j = next[j]; } } delete[] next; if (j == m) { return i - j; // 匹配成功，返回匹配的起始位置 } else { return -1; // 匹配失败，返回-1 } }
KMP算法的时间复杂度为O(n + m)，其中n为文本串的长度，m为模式串的长度。
4.1.3 Boyer-Moore算法
Boyer-Moore算法是一种高效的字符串匹配算法，它利用模式串的特点和右移规则，在匹配过程中跳过尽可能多的字符。
// Boyer-Moore算法示例代码 void buildBadCharTable(string pattern, int badCharTable[]) { int m = pattern.length(); for (int i = 0; i < 256; i++) { badCharTable[i] = m; } for (int i = 0; i < m - 1; i++) { badCharTable[pattern[i]] = m - 1 - i; } } int boyerMoore(string text, string pattern) { int n = text.length(); int m = pattern.length(); int* badCharTable = new int[256]; buildBadCharTable(pattern, badCharTable); int i = m - 1, j = m - 1; while (i < n) { if (text[i] == pattern[j]) { if (j == 0) { delete[] badCharTable; return i; // 匹配成功，返回匹配的起始位置 } i--; j--; } else { i += badCharTable[text[i]]; j = m - 1; } } delete[] badCharTable; return -1; // 匹配失败，返回-1 }
Boyer-Moore算法的时间复杂度为O(n + m)，其中n为文本串的长度，m为模式串的长度。
4.2 字符串编辑距离
字符串编辑距离是指通过一系列的插入、删除和替换操作，将一个字符串转换成另一个字符串所需的最少操作次数。常用的字符串编辑距离算法有Levenshtein距离、Damerau-Levenshtein距离等。
4.2.1 Levenshtein距离
Levenshtein距离，也称为编辑距离，是衡量两个字符串相似程度的指标。它定义为将一个字符串转换成另一个字符串所需的最少编辑操作次数，允许的操作包括插入、删除和替换。
// Levenshtein距离算法示例代码 int levenshteinDistance(string word1, string word2) { int m = word1.length(); int n = word2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { dp[i][0] = i; } for (int j = 1; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } return dp[m][n]; }
Levenshtein距离的时间复杂度为O(m * n)，其中m和n分别为两个字符串的长度。
4.2.2 Damerau-Levenshtein距离
Damerau-Levenshtein距离是Levenshtein距离的一种扩展，除了插入、删除和替换操作外，还允许相邻字符的交换操作。
// Damerau-Levenshtein距离算法示例代码 int damerauLevenshteinDistance(string word1, string word2) { int m = word1.length(); int n = word2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { dp[i][0] = i; } for (int j = 1; j <= n; j++) { dp[0][j] = j; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } if (i > 1 && j > 1 && word1[i - 1] == word2[j - 2] && word1[i - 2] == word2[j - 1]) { dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + 1); } } } return dp[m][n]; }
Damerau-Levenshtein距离的时间复杂度为O(m * n)，其中m和n分别为两个字符串的长度。
4.3 字符串压缩与解压缩
字符串压缩是指通过对字符串中重复出现的字符进行编码，减少字符串的存储空间。常用的字符串压缩算法有Run-Length Encoding（RLE）算法、Huffman编码等。
4.3.1 Run-Length Encoding（RLE）算法
Run-Length Encoding（RLE）算法是一种简单的无损压缩算法，它通过将连续出现的相同字符替换为字符和出现次数的组合来进行压缩。
// RLE算法示例代码 string compressRLE(string text) { int n = text.length(); if (n <= 1) { return text; } string compressed; int count = 1; for (int i = 1; i < n; i++) { if (text[i] == text[i - 1]) { count++; } else { compressed += text[i - 1] + to_string(count); count = 1; } } compressed += text[n - 1] + to_string(count); return compressed; }
4.3.2 Huffman编码
Huffman编码是一种变长编码方法，它通过根据字符出现的频率构建哈夫曼树，并根据哈夫曼树生成每个字符的编码。
// Huffman编码示例代码 struct TreeNode { char val; int freq; TreeNode* left; TreeNode* right; TreeNode(char c, int f) : val(c), freq(f), left(nullptr), right(nullptr) {} }; struct Compare { bool operator()(TreeNode* a, TreeNode* b) { return a->freq > b->freq; } }; void buildHuffmanTree(string text, unordered_map<char, int>& freqMap, priority_queue<TreeNode*, vector<TreeNode*>, Compare>& pq) { for (char c : text) { freqMap[c]++; } for (auto it = freqMap.begin(); it != freqMap.end(); it++) { TreeNode* node = new TreeNode(it->first, it->second); pq.push(node); } while (pq.size() > 1) { TreeNode* left = pq.top(); pq.pop(); TreeNode* right = pq.top(); pq.pop(); TreeNode* parent = new TreeNode('\0', left->freq + right->freq); parent->left = left; parent->right = right; pq.push(parent); } } void generateHuffmanCode(TreeNode* root, string code, unordered_map<char, string>& codeMap) { if (!root) { return; } if (!root->left && !root->right) { codeMap[root->val] = code; } generateHuffmanCode(root->left, code + "0", codeMap); generateHuffmanCode(root->right, code + "1", codeMap); } string compressHuffman(string text) { unordered_map<char, int> freqMap; priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq; buildHuffmanTree(text, freqMap, pq); unordered_map<char, string> codeMap; generateHuffmanCode(pq.top(), "", codeMap); string compressed; for (char c : text) { compressed += codeMap[c]; } return compressed; }
字符串解压缩与压缩相反，根据压缩后的字符串和相应的编码表进行解码即可。
以上是字符串处理方法的一些常用算法和示例代码，通过学习这些算法，可以更好地理解和应用字符串处理技术。在实际的软件设计师考试中，掌握这些知识点将有助于解答相关问题和完成相应的编程任务。
第五章：其他常用算法
5.1 贪心算法
5.1.1 原理及步骤
贪心算法是一种通过每一步的局部最优选择来达到全局最优的算法。其基本思想是在每一步选择中都做出当前状态下最优的选择，而不考虑之后的结果。贪心算法一般可以分为以下步骤：
- 定义问题的解空间和解空间的度量准则。
- 利用贪心的策略进行选择，即每一步都选择当前最优解。
- 判断当前选择是否满足问题的约束条件，如果满足，则进入下一步；如果不满足，则回溯到上一步重新选择。
- 重复步骤2和3，直到达到问题的终止条件。
5.1.2 时间复杂度和空间复杂度
贪心算法的时间复杂度一般较低，通常为O(nlogn)或O(n)，其中n为问题的规模。空间复杂度则取决于具体的算法实现。
5.1.3 应用场景和优化方法
贪心算法常用于求解最优化问题，例如霍夫曼编码、最小生成树、任务调度等。在实际应用中，需要注意贪心策略是否能够得到全局最优解，有时候需要进行优化方法的改进。
以下是一个示例代码，展示了贪心算法在任务调度问题中的应用：
#include <iostream> #include <vector> #include <algorithm> // 定义任务结构体 struct Task { int start; int end; }; // 比较函数，按照任务结束时间进行排序 bool compare(Task t1, Task t2) { return t1.end < t2.end; } // 贪心算法求解任务调度问题 std::vector<Task> scheduleTasks(std::vector<Task>& tasks) { std::vector<Task> result; // 按照任务结束时间进行排序 std::sort(tasks.begin(), tasks.end(), compare); // 选择第一个任务 result.push_back(tasks[0]); int lastEnd = tasks[0].end; // 依次选择后续任务 for (int i = 1; i < tasks.size(); i++) { if (tasks[i].start >= lastEnd) { result.push_back(tasks[i]); lastEnd = tasks[i].end; } } return result; } int main() { std::vector<Task> tasks = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}, {12, 14}}; std::vector<Task> result = scheduleTasks(tasks); std::cout << "最优任务调度结果：" << std::endl; for (auto task : result) { std::cout << "开始时间：" << task.start << "，结束时间：" << task.end << std::endl; } return 0; }
【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（三）https://developer.aliyun.com/article/1467574
