c++ 实现在给定字符串中搜索并返回子字符串个数的函数
时间: 2023-06-19 22:04:24 浏览: 122
可以使用字符串查找算法来实现在给定字符串中搜索并返回子字符串个数的函数。比较常用的算法是KMP算法和Boyer-Moore算法。
下面是使用KMP算法实现的代码示例:
```cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> getNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
int countSubstring(const string& str, const string& pattern) {
int n = str.length(), m = pattern.length();
vector<int> next = getNext(pattern);
int res = 0;
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && str[i] != pattern[j]) {
j = next[j - 1];
}
if (str[i] == pattern[j]) {
j++;
}
if (j == m) {
res++;
j = next[j - 1];
}
}
return res;
}
int main() {
string str = "aabaaabaaac";
string pattern = "aa";
int count = countSubstring(str, pattern);
cout << count << endl; // 输出 4
return 0;
}
```
在上面的代码中,`getNext`函数用来计算模式串的next数组,`countSubstring`函数用来计算字符串中子串的个数。具体实现过程中,我们需要两个指针i和j,分别指向字符串和模式串。当str[i]和pattern[j]不匹配时,我们需要用next数组来更新j的值,直到str[i]和pattern[j]匹配为止。当j等于模式串的长度时,说明找到了一个匹配的子串,此时将结果加1,并更新j的值为next[j-1]。
阅读全文