在 C++ 中實現(xiàn)自定義的字符串匹配規(guī)則,你可以使用以下幾種方法:
遍歷目標字符串,逐個字符與模式字符串進行比較。這種方法的時間復(fù)雜度較高,為 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;
}
KMP 算法是一種高效的字符串匹配算法,時間復(fù)雜度為 O(n+m)。它通過預(yù)處理模式字符串,避免在不匹配時重新檢查已匹配的字符。
#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;
}
BM 算法是一種快速的字符串匹配算法,平均時間復(fù)雜度為 O(n+m)。它通過跳過一些不匹配的字符來減少匹配次數(shù)。
#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;
}
這些方法可以實現(xiàn)自定義的字符串匹配規(guī)則。你可以根據(jù)自己的需求選擇合適的方法。