一、朴素匹配算法（Naive Algorithm）
朴素字符串匹配算法是一种非常直观的字符串匹配算法，基本的思想是将待查找字符串的每一个字符与目标字符串的每一个字符逐一比较，这也是为何它被称为“朴素”的原因。由于它涉及到两层嵌套循环，因此其时间复杂度为O(mn)，m和n分别为目标字符串和待查找字符串的长度。
朴素匹配算法C++代码示例：
#include <iostream> #include <string> void search(std::string pat, std::string txt) { int M = pat.length(); int N = txt.length(); for (int i = 0; i <= N - M; i++) { int j; for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break; if (j == M) std::cout << "Pattern found at index " << i << std::endl; } } int main() { std::string txt = "ABABDABACDABABCABAB"; std::string pat = "ABABCABAB"; search(pat, txt); return 0; }
代码实现步骤：
- 创建一个包含主字符串和目标字符串的程序，并定义搜索函数。
- 在搜索函数中，遍历主字符串，每次移动一步。对于主字符串中的每一个子字符串，如果该子字符串与目标字符串相等，则打印出该子字符串在主字符串中的位置。
- 主函数调用这个搜索函数，传入主字符串和目标字符串作为参数。
二、KMP算法（Knuth-Morris-pratt- Algorithm）
KMP算法（Knuth-Morris-Pratt算法）是一种改进后的字符串匹配算法。相较于朴素匹配算法，在匹配失败时，通过预先计算目标字符串的部分匹配表，可以避免回溯以提高匹配效率。KMP算法的时间复杂度是O(m+n)，其中m和n分别代表目标字符串和待查找字符串的长度。
KMP算法C++代码示例：
#include <iostream> #include <string> #include <vector> std::vector<int> computeLPSArray(std::string pat) { int M = pat.length(); std::vector<int> lps(M); int len = 0; lps[0] = 0; int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; } void KMPSearch(std::string pat, std::string txt) { int M = pat.length(); int N = txt.length(); std::vector<int> lps = computeLPSArray(pat); int i = 0; int j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { std::cout << "Pattern found at index " << (i - j) << std::endl; j = lps[j - 1]; } else if (i < N && pat[j] != txt[i]) { if (j != 0) j = lps[j - 1]; else i++; } } } int main() { std::string txt = "ABABDABACDABABCABAB"; std::string pat = "ABABCABAB"; KMPSearch(pat, txt); return 0; }
代码实现步骤：
1. 创建一个计算部分匹配数组（也称为最长公共前后缀数组）的函数`computeLPSArray()`。该函数计算目标字符串的部分匹配值。在函数中，初始化目标字符串的长度，部分匹配表的第一个元素设为0。然后通过遍历目标字符串，利用两个指针找出最大的匹配前后缀值，并填充部分匹配数组。
2. 在KMPSearch函数中，首先计算目标字符串的部分匹配数组。然后遍历待查找字符串，使用两个指针i和j分别指向主字符串和模式串。比较当前字符，若匹配则两指针同时后移。否则，根据部分匹配表调整模式串指针j的位置。当匹配成功时，输出模式串在主串的起始位置。
3. 在主函数中，调用KMPSearch函数，并传入待查找字符串和目标字符串作为参数。
三、Rabin-karp算法
Rabin-Karp算法是一种基于哈希的字符串匹配算法。利用哈希函数计算待查找字符串和目标字符串的哈希值，仅在哈希值匹配时才进行字符级别的比较。Rabin-Karp算法通常的情况下的平均时间复杂度为O(m+n)，其中m代表目标字符串长度，n代表待查找字符串长度。最坏的情况下，时间复杂度也有可能为O(mn)。
Rabin-Karp算法C++代码示例：
#include <iostream> #include <string> #define prime 101 long long create_hash_value(const std::string &str, int end) { long long hash_val = 0; for (int i = 0; i <= end; i++) { hash_val += str[i] * pow(prime, i); } return hash_val; } long long recalculate_hash(const std::string &str, int old_index, int new_index, long long old_hash, int pattern_length) { long long new_hash = old_hash - str[old_index]; new_hash /= prime; new_hash += str[new_index] * pow(prime, pattern_length - 1); return new_hash; } bool checkEqual(const std::string &str1, int start1, const std::string &str2, int start2, int length) { for (int i = 0; i < length; i++) { if (str1[start1 + i] != str2[start2 + i]) { return false; } } return true; } void RabinKarpSearch(const std::string &pattern, const std::string &text) { int m = pattern.length(); int n = text.length(); long long pattern_hash = create_hash_value(pattern, m - 1); long long text_hash = create_hash_value(text, m - 1); for (int i = 1; i <= n - m + 1; i++) { if (pattern_hash == text_hash && checkEqual(pattern, 0, text, i - 1, m)) { std::cout << "Pattern found at index " << i - 1 << std::endl; } if (i < n - m + 1) { text_hash = recalculate_hash(text, i - 1, i + m - 1, text_hash, m); } } } int main() { std::string text = "ABABDABACDABABCABAB"; std::string pattern = "ABABCABAB"; RabinKarpSearch(pattern, text); return 0; }
代码实现步骤：
1. 定义一个用于计算字符串哈希值的函数`create_hash_value()`，提供字符串和结束字符位置作为参数。使用循环遍历字符串计算哈希值。
2. 定义一个`recalculate_hash()`函数，用于计算滚动哈希值。提供原字符串、旧哈希值、旧字符索引，新字符索引和模式串长度作为参数。
3. 定义一个辅助函数`checkEqual()`，在哈希值匹配的情况下进行逐个字符的比较，以确定字符串是否相等。
4. 使用`RabinKarpSearch()`函数实现Rabin-Karp算法。首先计算模式串的哈希值和主串前m个字符的哈希值。遍历主串，并在哈希值匹配且字符串相等时输出匹配位置。接下来计算下一个窗口的哈希值，直到遍历完整个主串。
5. 在主函数中，调用`RabinKarpSearch()`函数并传入待查找字符串和目标字符串作为参数。
四、Ooyer-Moore算法
Boyer-Moore算法是一种高效的字符串匹配算法，它摒弃了从前向后的匹配方式，转向从后向前的匹配。当字符不匹配时，根据“坏字符规则”和“好后缀规则”进行模式串的位移，以减少多余的比较次数，从而提高匹配效率。Boyer-Moore算法的预处理时间复杂度为O(m)（m代表目标字符串长度），最好的情况下匹配时间复杂度为O(n/m)，最坏的情况下为O(n)（n为待查找字符串的长度）。
Boyer-Moore算法的一个精简C++实现（简化至只使用坏字符规则的版本）：
#include<bits/stdc++.h> #define NO_OF_CHARS 256 int max(int a, int b) { return (a > b)? a: b; } void badCharHeuristic( char *str, int size, int badchar[NO_OF_CHARS]) { int i; for (i = 0; i < NO_OF_CHARS; i++) badchar[i] = -1; for (i = 0; i < size; i++) badchar[(int) str[i]] = i; } void search( char *txt, char *pat) { int m = strlen(pat); int n = strlen(txt); int badchar[NO_OF_CHARS]; badCharHeuristic(pat, m, badchar); int s = 0; while(s <= (n - m)) { int j = m-1; while(j >= 0 && pat[j] == txt[s+j]) j--; if (j < 0) { printf("\n pattern occurs at shift = %d", s); s += (s+m < n)? m-badchar[txt[s+m]] : 1; } else s += max(1, j - badchar[txt[s+j]]); } } int main() { char txt[] = "ABAAABCD"; char pat[] = "ABC"; search(txt, pat); return 0; }
代码实现步骤：
1. 定义`max`函数，用于在后续步骤中判断并返回两数中的最大值。
2. 定义`badCharHeuristic`函数，用于预处理并创建坏字符规则所需的坏字符表。创建并初始化一个大小为字符集的数组，将数组中所有的位置设置为-1。随后遍历目标字符串，根据每个字符的ASCII值作为索引将其在目标字符串中的位置（相对于字符串尾部的位置）存入数组。
3. 创建`search`函数，实现Boyer-Moore算法。首先计算目标字符串和待查找字符串的长度，然后调用`badCharHeuristic`函数创建坏字符表。使用变量s跟踪模
五、Sunday算法
Sunday算法是一种字符串匹配算法，与Boyer-Moore算法有些类似，但比它更加简单。Sunday算法也可以实现在O(n)的时间复杂度内完成字符串匹配（n代表待查找字符串长度），预处理时间复杂度是O(m+σ)，其中m代表目标字符串长度，σ代表字符集大小。在Sunday算法中，主要利用了一种称为“偏移表”的结构来确定模式字符串的跳转步数。
Sunday算法C++代码示例：
#include<iostream> #include<string> #include<vector> #define NO_OF_CHARS 256 using namespace std; vector<int> makeOffsetTable(string pat) { int m = pat.length(); vector<int> table(NO_OF_CHARS, m+1); for (int i = 0; i < m; ++i) table[(int)pat[i]] = m - i; return table; } void SundaySearch(string txt, string pat) { vector<int> table = makeOffsetTable(pat); int m = pat.length(); int n = txt.length(); int i = 0; while (i <= n - m) { if (txt.substr(i, m) == pat) { cout << "Pattern found at index " << i << endl; } i += table[txt[i+m]]; } } int main() { string txt = "ABCDABCDABEE"; string pat = "ABCDABE"; SundaySearch(txt, pat); return 0; }
代码实现步骤：
1. 首先定义函数`makeOffsetTable`来创建Sunday算法所需的偏移表。这里创建了一个大小为字符集大小的数组，将每个位置初始化为模式字符串长度加一。然后遍历模式字符串，将每个字符在模式字符串中的“偏移值”保存到它的ASCII值对应的数组位置。
2. 定义主要的函数`SundaySearch`，先根据模式串构造偏移表。然后遍历主串进行匹配，每次匹配模式串长度的子串，如果匹配成功则打印匹配位置。接着根据偏移表中对应于主字符串中位于当前匹配串后一位的字符的偏移值确定下一轮匹配的起始位置。
3. 在主函数中，调用`SundaySearch()`函数并传入待查找字符串和目标字符串作为参数。
六、Aho-Corasick算法
Aho-Corasick算法是一种字符串匹配的算法，主要用于在主串中查找多个模式串。该算法的主要优点是它能在O(n + m + z)时间内完成所有模式串的查找，其中n为主串长度，m为所有模式串的总长度，z为匹配的模式串数量。主要利用字典树（Trie）数据结构和状态机的概念来提高匹配的效率。
Aho-Corasick算法C++代码示例：
#include<bits/stdc++.h> using namespace std; const int ALPHABET_SIZE = 26; struct AcNode { AcNode *children[ALPHABET_SIZE]; bool isEndOfWord; AcNode *failure; int occurrences; }; AcNode *getNode(void) { AcNode *pNode = new AcNode; pNode->isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) pNode->children[i] = NULL; return pNode; } void insert(AcNode *root, string key) { AcNode *pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } pCrawl->isEndOfWord = true; } void buildFailureLinks(AcNode *root) { queue<AcNode*> q; if (root) { root->failure = root; q.push(root); } while (!q.empty()) { AcNode *node = q.front(); q.pop(); for (int i = 0; i < ALPHABET_SIZE; ++i) { AcNode *child = node->children[i]; if (!child) continue; AcNode *best = node->failure; while (best != root && !best->children[i]) best = best->failure; if (best->children[i]) best = best->children[i]; child->failure = best; q.push(child); } } } void search(AcNode *root, string key) { AcNode *crawl = root; for (int i = 0; i < key.length(); i++) { while (crawl != root && !crawl->children[key[i] - 'a']) crawl = crawl->failure; if (crawl->children[key[i] - 'a']) crawl = crawl->children[key[i] - 'a']; AcNode *temp = crawl; while (temp != root && temp->isEndOfWord) { cout << "Found pattern" << endl; temp = temp->failure; } } } int main() { string patterns[] = {"he", "she", "yours", "hers"}; AcNode *root = getNode(); for(int i = 0; i < 4; ++i) insert(root, patterns[i]); buildFailureLinks(root); search(root, "yourshehersherssheshehersyours"); return 0; }
代码实现步骤：
1. 定义结构AcNode，其中的children数组用于存储各个子结点，isEndOfWord标识是否为单词的终点，failure指向失配时应该跳转的结点。
2. 定义getNode函数创建一个新的结点。
3. 创建insert函数，用于插入一个模式串到字典树中。
4. 创建buildFailureLinks函数，用于构建每一个结点失配时的跳转结点，利用广度优先搜索，比较每个结点的失配结点的孩子中是否存在可以直接跳转的。
5. 创建search函数，在字典树中查找主串中的模式串，当发生失配时，转向失配结点继续查找。
6. 在主函数中创建字典树的根结点，插入模式串，构建跳转结点，开始搜索。
