给出可复制的代码,谢谢
时间: 2024-10-24 07:01:12 浏览: 22
当然,下面是一个简单的C++示例,展示了使用Brute Force和KMP算法分别查找文本中的模式的例子:
```cpp
#include <iostream>
#include <string>
// Brute Force (BF) algorithm
bool bruteForceMatch(const std::string& text, const std::string& pattern) {
size_t i = 0, j = 0;
while (i < text.length() && j < pattern.length()) {
if (text[i] == pattern[j]) {
i++;
j++;
} else {
i = i == 0 ? 0 : i + 1;
}
}
return j == pattern.length();
}
// Knuth-Morris-Pratt (KMP) algorithm
size_t buildPatternFailures(const std::string& pattern) {
size_t n = pattern.size(), fail[n];
for (size_t i = 1; i < n; ++i) {
fail[i] = fail[i - 1];
while (fail[i] > 0 && pattern[i] != pattern[fail[i]]) {
fail[i] = fail[fail[i] - 1];
}
if (pattern[i] == pattern[fail[i]]) {
fail[i]++;
}
}
return fail;
}
bool kmpMatch(const std::string& text, const std::string& pattern) {
size_t n = text.size(), m = pattern.size();
size_t i = 0, j = 0;
size_t fail = buildPatternFailures(pattern);
while (i < n && j < m) {
if (text[i] == pattern[j]) {
i++;
j++;
} else if (j > 0) {
j = fail[j - 1];
} else {
i++;
}
}
return j == m;
}
int main() {
std::string text = "ababcabccabccacbab";
std::string pattern = "abccac";
bool bfResult = bruteForceMatch(text, pattern);
bool kmpResult = kmpMatch(text, pattern);
if (bfResult) {
std::cout << "Brute Force found match at position " << /* calculate the position */ << std::endl;
}
if (kmpResult) {
std::cout << "KMP found match at position " << /* calculate the position */ << std::endl;
}
return 0;
}
```
这个代码首先实现了BF和KMP算法,并在`main()`函数中应用它们到给定的文本和模式上。请注意,实际的匹配位置需要根据算法的具体实现计算。
阅读全文