直接使用find函数来查找字符串中的字串

#include<bits/stdc++.h>
using namespace std;
int main() {
	string c,s;
	cin>>s>>c;
	int index = 0;
    int sum = 0;
    while ((index = s.find(c,index)) != string::npos) {
      index ++;
      sum++;
    }
    cout << sum << endl;
    return 0;
}

字符串Hash：O(N) 的复杂度

对主串构造hash前缀，对目标串求hash值。

#include <bits/stdc++.h>
using namespace std;
const int base = 131;
const int N = 1e6 + 3;
using ll = long long;
ll h[N], b[N];

ll gethash(int l,int r)
{
  return h[r] - h[l-1]*b[r-l+1];
}

int main()
{
  string s;
  string target;
  cin>>s;
  cin>>target;
  b[0] = 1;
  ll key = 0;
  for(int i = 0;i<target.length();i++)
  {
    key = (key*base + target[i] - 'a' + 1);
  }
  for(int i = 0;i<s.length();i++)
  {
    h[i+1] = (h[i]*base + s[i] - 'a' + 1);
    b[i+1] = b[i]*base;
  }
  int cnt = 0;
  for(int i = 0;i + target.length()<=s.length();i++)
  {
    if(gethash(i + 1, i + target.length()) == key)
    cnt++;
  }
  cout<<cnt;
}

#include<bits/stdc++.h> using namespace std;

int main(){ string A,B; getline(cin,A); getline(cin,B); long long sum=0; for(long long i=0;i<A.length();i++){ int pos= A.find(B,i); if(pos!=string::npos){ sum++; i=pos; } else{ break; } } cout<<sum;

return 0;

}

// https://dashoj.com/p/74
#include <bits/stdc++.h>

using namespace std;

int main() {
	string text, pattren;
	cin >> text >> pattren;
	string str = pattren + '#' + text;
	vector<int> pi(str.size(), 0);
	for (int i = 1; i < str.size(); i++) {
		int len = pi[i - 1];
		while (len != 0 && str[i] != str[len]) len = pi[len - 1];
		if (str[i] == str[len]) pi[i] = len + 1;
	}
	sort(pi.begin(), pi.end(), [](int a, int b) {
		return a > b;
	});
	int cnt = 0, max = pi[0];
	for (int i : pi) if (i == max) cnt++; else break;
	cout << cnt << endl;
	return 0;
}

kmp算法

#include<cstdio>
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
static int next_table[N];

void nexttable(string s, int len) {
	int p = 0, i = 1;
	next_table[0] = 0;
	while (i < len) {
		if (s[i] == s[p]) {
			p++;
			next_table[i] = p;
			i++;
		}
		else {
			if (p != 0) {
				p = next_table[p-1];
			}
			else {
				next_table[i] = p;
				i++;
			}
		}
	}

	for (int i = len - 1; i > 0; i--) next_table[i] = next_table[i - 1];
	next_table[0] = -1;

}

int kmp(string bigs, string s, int len) {
	int count = 0;
	int m = bigs.length();
	int i = 0, j = 0;
	while (j < m) {
		if (i == len - 1 && s[i] == bigs[j]) {
			count++;
			i = next_table[i];
		}

		if (s[i] == bigs[j]) {
			i++; j++;
		}
		else {
			if (next_table[i] == -1) {
				j++;
			}
			else i = next_table[i];

		}
	}
	return count;

}

int main() {
	string bigs, s;
	cin >> bigs >> s;
	int len = s.length();
	nexttable(s, len);

	cout << kmp(bigs, s, len);
	return 0;
}