怎样在c++中实现自定义的字符串匹配规则

在 C++ 中实现自定义的字符串匹配规则，你可以使用以下几种方法：

1. 暴力匹配（Brute Force）

遍历目标字符串，逐个字符与模式字符串进行比较。这种方法的时间复杂度较高，为 O(n*m)，其中 n 和 m 分别为目标字符串和模式字符串的长度。

#include <iostream> #include <string>  bool isMatch(const std::string& target, const std::string& pattern) {     int n = target.size();     int m = pattern.size();      for (int i = 0; i <= n - m; ++i) {         bool match = true;         for (int j = 0; j < m; ++j) {             if (target[i + j] != pattern[j]) {                 match = false;                 break;             }         }         if (match) {             return true;         }     }     return false; }  int main() {     std::string target = "hello";     std::string pattern = "ll";     std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;     return 0; } 

2. KMP 算法（Knuth-Morris-Pratt）

KMP 算法是一种高效的字符串匹配算法，时间复杂度为 O(n+m)。它通过预处理模式字符串，避免在不匹配时重新检查已匹配的字符。

#include <iostream> #include <string>  std::vector<int> computePrefixFunction(const std::string& pattern) {     int m = pattern.size();     std::vector<int> pi(m, 0);     int k = 0;      for (int q = 1; q < m; ++q) {         while (k > 0 && pattern[k] != pattern[q]) {             k = pi[k - 1];         }         if (pattern[k] == pattern[q]) {             ++k;         }         pi[q] = k;     }     return pi; }  bool isMatch(const std::string& target, const std::string& pattern) {     int n = target.size();     int m = pattern.size();     std::vector<int> pi = computePrefixFunction(pattern);      int q = 0;     for (int i = 0; i < n; ++i) {         while (q > 0 && pattern[q] != target[i]) {             q = pi[q - 1];         }         if (pattern[q] == target[i]) {             ++q;         }         if (q == m) {             return true;         }     }     return false; }  int main() {     std::string target = "hello";     std::string pattern = "ll";     std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;     return 0; } 

3. BM 算法（Boyer-Moore）

BM 算法是一种快速的字符串匹配算法，平均时间复杂度为 O(n+m)。它通过跳过一些不匹配的字符来减少匹配次数。

#include <iostream> #include <string>  std::string badCharacterTable(const std::string& pattern) {     int m = pattern.size();     std::string badCharTable(m, 0);      for (int i = 0; i < m; ++i) {         badCharTable[pattern[i]] = i;     }     return badCharTable; }  std::string goodSuffixTable(const std::string& pattern, const std::string& badCharTable) {     int m = pattern.size();     std::string goodSuffixTable(m, 0);     int k = 0;      for (int i = m - 1; i >= 0; --i) {         while (k > 0 && pattern[k] != pattern[i]) {             k = badCharTable[pattern[k]];         }         if (pattern[k] == pattern[i]) {             ++k;         }         goodSuffixTable[i] = k;     }     return goodSuffixTable; }  bool isMatch(const std::string& target, const std::string& pattern) {     int n = target.size();     int m = pattern.size();     std::string badCharTable = badCharacterTable(pattern);     std::string goodSuffixTable = goodSuffixTable(pattern, badCharTable);      int i = 0;     int j = 0;     while (i < n) {         if (j > 0 && pattern[j] != target[i]) {             j = goodSuffixTable[j - 1];         }         if (pattern[j] == target[i]) {             ++i;             ++j;         } else if (j == 0) {             ++i;         } else {             j = badCharTable[pattern[j]];         }     }     return j == m; }  int main() {     std::string target = "hello";     std::string pattern = "ll";     std::cout << (isMatch(target, pattern) ? "匹配成功" : "匹配失败") << std::endl;     return 0; } 

这些方法可以实现自定义的字符串匹配规则。你可以根据自己的需求选择合适的方法。