设计匹配算法,实现下面字符串的匹配。若匹配成功,返回匹配成功的序号,若匹配失败,返回失败信息。 text ="我家门前有两棵树,一棵是枣树,还有一棵也是枣树" pattern ="枣树" 要求:1.使用C++语言设计算法 2.通过键盘输入的方式为text、pattern赋值
时间: 2024-09-21 09:10:27 浏览: 24
在C++中,我们可以使用KMP(Knuth-Morris-Pratt)算法或者Boyer-Moore算法来实现高效的字符串匹配。这里我将演示如何使用KMP算法,因为它不需要预处理模式串,并且对于这个问题来说效率较高。
首先,我们定义KMP表(也称为部分前缀函数),用于存储模式串中每个位置之前的最长公共前后缀长度:
```cpp
#include <string>
#include <vector>
std::vector<int> getKMPPrefix(const std::string& pattern) {
int len = pattern.length();
std::vector<int> lps(len, 0);
int j = -1;
for (int i = 1; i < len; ++i) {
while (j > -1 && pattern[i] != pattern[j + 1]) {
j = lps[j];
}
if (pattern[i] == pattern[j + 1]) {
++j;
}
lps[i] = j;
}
return lps;
}
int KMPMatch(const std::string& text, const std::string& pattern) {
int n = text.length(), m = pattern.length();
std::vector<int> lps = getKMPPrefix(pattern);
int i = 0, j = 0;
while (i < n) {
if (text[i] == pattern[j]) {
++i;
++j;
} else if (j > 0) {
j = lps[j - 1];
} else {
++i;
}
if (j == m) {
return i - j;
}
}
// 如果没有找到匹配,则返回“匹配失败”
return "匹配失败";
}
```
为了通过键盘输入的方式为`text`和`pattern`赋值,你可以创建一个简单的主函数来获取用户输入:
```cpp
int main() {
std::string text, pattern;
std::cout << "请输入文本(text): ";
getline(std::cin, text);
std::cout << "请输入模式(pattern): ";
getline(std::cin, pattern);
std::string result = KMPMatch(text, pattern);
if (result == "匹配失败") {
std::cout << "匹配失败\n";
} else {
std::cout << "匹配成功,从第" << result << "个字符开始\n";
}
return 0;
}
```
运行此程序后,用户可以依次输入`text`和`pattern`,然后它会返回匹配结果。如果没有匹配,会显示“匹配失败”。