给你一个目标串,请查找在给目标串中是否存在模式串,存在就输出第一个模式串在目标串中出现的位置。 输入 占两行,第一行是目标串(长度小于1000),第二行为模式串(长度小于100)。 输出 输出模式串在目标串中出现的位置,即模式串匹配到目标串时第一个字符在目标串的位置(注意从1开始描述字符开始位置),不能匹配时输出0.请使用c++语言。 样例输入 复制 appleorange orange 样例输出 复制 6
时间: 2024-03-21 11:39:57 浏览: 44
好的,这是一个字符串匹配的问题。可以使用字符串匹配算法来解决,本题可以使用 KMP 算法实现。下面是一个 C++ 代码示例:
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 计算模式串的前缀数组
vector<int> compute_prefix(string pattern) {
int m = pattern.length();
vector<int> prefix(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = prefix[j-1];
}
if (pattern[i] == pattern[j]) {
j++;
}
prefix[i] = j;
}
return prefix;
}
// 使用 KMP 算法匹配模式串
int kmp_search(string text, string pattern) {
int n = text.length();
int m = pattern.length();
vector<int> prefix = compute_prefix(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = prefix[j-1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
return i-m+2; // 返回匹配的位置,从1开始
}
}
return 0; // 没有找到匹配的子串
}
int main() {
string text, pattern;
getline(cin, text);
getline(cin, pattern);
int pos = kmp_search(text, pattern);
cout << pos << endl;
return 0;
}
```
这个代码中,我们定义了两个函数。`compute_prefix` 函数用于计算模式串的前缀数组。`kmp_search` 函数使用 KMP 算法匹配模式串。在主程序中,我们读入两行字符串,第一行为目标串,第二行为模式串。然后调用 `kmp_search` 函数来查找模式串在目标串中的位置,并输出结果。注意,在 C++ 中读入一行字符串需要使用 `getline(cin, s)`,其中 `s` 是一个字符串变量。
阅读全文