C++如何统计字符串中子串出现的次数 |holyya.com

C++如何统计字符串中子串出现的次数

2023-07-06 09:54:26 深夜i -- --

C++ 统计字符串子串出现次数

在C++中，统计一个字符串中某个子串出现的次数是一个基本的问题。本文将介绍一些常见的方法来实现这个功能。

方法1：暴力枚举法

这是最朴素的方法，也是最易懂的方法之一。它的原理是逐一枚举每一个子串，判断它是否和目标子串相同。如果相同，计数器加1。这种方法时间复杂度较高，但适用于简单的情况。

以下是代码示例：


#include <iostream>
using namespace std;
int count_substring(const string& s, const string& target) {
  int count = 0;
  for (int i = 0; i <= (int)s.size() - (int)target.size(); ++i) {
    bool flag = true;
    for (int j = 0; j < (int)target.size(); ++j) {
      if (s[i + j] != target[j])
        flag = false;
        break;
      
    }
    if (flag) ++count;
  }
  return count;
}
int main() {
  string s, target;
  cin >> s >> target;
  cout << count_substring(s, target) << endl;
  return 0;
}

方法2：KMP算法

KMP算法是一种高效的字符串匹配算法，它的主要思想是利用已知信息来避免比较重复字符，从而提高匹配速度。

以下是代码示例：


#include <iostream>
#include <vector>
using namespace std;
vector<int> get_next(const string& target) {
  int n = target.size();
  vector<int> next(n + 1);
  next[0] = -1;
  int i = 0, j = -1;
  while (i < n) {
    if (j == -1 || target[i] == target[j]) {
      ++i;
      ++j;
      next[i] = j;
    } else {
      j = next[j];
    }
  }
  return next;
}
int count_substring(const string& s, const string& target) {
  int count = 0;
  vector<int> next = get_next(target);
  int i = 0, j = 0, n = s.size(), m = target.size();
  while (i < n) {
    if (j == -1 || s[i] == target[j]) {
      ++i;
      ++j;
    } else {
      j = next[j];
    }
    if (j == m) {
      ++count;
      j = next[j];
    }
  }
  return count;
}
int main() {
  string s, target;
  cin >> s >> target;
  cout << count_substring(s, target) << endl;
  return 0;
}

方法3：标准库函数

C++标准库中有一个函数`std::count`可以用来统计子串出现的次数。它的使用非常简单，只需调用一次即可。

以下是代码示例：


#include <iostream>
#include <algorithm>
using namespace std;
int count_substring(const string& s, const string& target) {
  int count = 0;
  auto it = s.begin();
  while (it != s.end()) {
    it = search(it, s.end(), target.begin(), target.end());
    if (it != s.end()) {
      ++count;
      it += target.size();
    }
  }
  return count;
}
int main() {
  string s, target;
  cin >> s >> target;
  cout << count_substring(s, target) << endl;
  return 0;
}

上述三种方法中，KMP算法的效率最高，但也最复杂。选择哪种方法取决于具体情况，需要根据实际需求进行权衡和选择。

上一篇: idea打包java可执行jar包

下一篇: C++求任意数的位数和

评论区

()

相似文章