这是一个关于字符串操作的问题,题目中要求判断子串sub是否存在于主串s中,如果存在,则返回子串在主串中的起始位置;如果不存在,则返回-1。同时,题目要求输入主串s和子串sub,并输出子串在主串中的起始位置以及出现的次数。
时间: 2024-02-28 21:56:47 浏览: 49
好的,这是一个字符串匹配问题,可以使用字符串匹配算法来解决。以下是一个 C++ 的示例代码,其中使用了 KMP 算法来实现字符串匹配:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 计算 next 数组
void getNext(const string& sub, vector<int>& next) {
int m = sub.size();
int j = 0, k = -1;
next[0] = -1;
while (j < m - 1) {
if (k == -1 || sub[j] == sub[k]) {
j++;
k++;
next[j] = k;
} else {
k = next[k];
}
}
}
// KMP 算法
int kmp(const string& s, const string& sub) {
int n = s.size(), m = sub.size();
vector<int> next(m);
getNext(sub, next);
int i = 0, j = 0, cnt = 0, pos = -1;
while (i < n && j < m) {
if (j == -1 || s[i] == sub[j]) {
i++;
j++;
} else {
j = next[j];
}
if (j == m) {
cnt++;
if (pos == -1) {
pos = i - m;
}
j = next[j-1];
}
}
cout << "子串在主串中的起始位置:" << pos << endl;
cout << "子串在主串中出现的次数:" << cnt << endl;
return pos;
}
int main() {
string s, sub;
cout << "请输入主串:" << endl;
cin >> s;
cout << "请输入子串:" << endl;
cin >> sub;
int pos = kmp(s, sub);
if (pos == -1) {
cout << "子串不存在于主串中" << endl;
} else {
cout << "子串存在于主串中,其起始位置为:" << pos << endl;
}
return 0;
}
```
在上面的代码中,getNext 函数用于计算子串的 next 数组,kmp 函数用于实现 KMP 算法,并输出子串在主串中的起始位置和出现次数。主函数中,先输入主串和子串,然后调用 kmp 函数进行匹配,最后根据返回值判断子串是否存在于主串中。
阅读全文