C++14(g++5.4) 解法, 执行用时: 66ms, 内存消耗: 2456K, 提交时间: 2019-11-17 19:13:05

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


int main() {
  string A, B; cin >> A >> B;
  vector<unsigned> base(B.size()+1);
  base[0] = 1;
  for (int i = 1; i < base.size(); i++) base[i] = base[i - 1] * 33;
  unsigned hb = 0;
  for (int i = 0; i < B.size(); i++) {
    hb = hb * 33 + B[i];
  }
  int cnt = 0;
  unsigned ha = 0;
  for (int i = 0; i < A.size(); i++) {
    ha = ha * 33 + A[i];
    if (i - int(B.size()) >= 0) ha -= base.back() * A[i - B.size()];
    if (i - int(B.size() - 1) >= 0 && ha == hb) cnt++;
  }
  cout << cnt << endl;
}

C++(g++ 7.5.0) 解法, 执行用时: 27ms, 内存消耗: 2584K, 提交时间: 2023-07-13 17:21:36

#include <bits/stdc++.h>
#define N 1111111
using namespace std;
int ne[N];
char s[N], p[N];
int main()
{
	cin >> s + 1;
	cin >> p + 1;
	int n = strlen(s + 1), m = strlen(p + 1);
	for(int i = 2, j = 0; i <= m; i++)
	{
		while(j && p[i] != p[j + 1]) j = ne[j];
		if(p[i] == p[j + 1]) j++;
		ne[i] = j;
	}
	int cnt = 0;
	for(int i = 1, j = 0; i <= n; i++)
	{
		while(j && s[i] != p[j + 1]) j = ne[j];
		if(s[i] == p[j + 1]) j++;
		if(j == m)
		{
			cnt++;
//			cout << i << " " << j << "\n";
			j = ne[j];
		}
	}
	cout << cnt;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 30ms, 内存消耗: 2484K, 提交时间: 2023-07-12 10:06:47

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s,p;
int ne[N],ans=0;
int main(){
	ne[0]=-1;
	cin>>s>>p;
	for(int i=1,j=-1;i<p.size();i++){
		while(j!=-1&&p[i]!=p[j+1]){
			j=ne[j];
		}
		if(p[i]==p[j+1]){
			j++;
		}
		ne[i]=j;
	}
	for(int i=0,j=-1;i<s.size();i++){
		while(j!=-1&&s[i]!=p[j+1]){
			j=ne[j];
		}
		if(s[i]==p[j+1]){
			j++;
		}
		if(j==p.size()-1){
			ans++;
			j=ne[j];
		}
	}
	cout<<ans;
	return 0;
}

Go(1.14.4) 解法, 执行用时: 1142ms, 内存消耗: 6896K, 提交时间: 2020-11-07 17:54:54

package main

import (
	"fmt"
	"strings"
)

func main() {
	var s1,s2 string
	fmt.Scan(&s1)
	fmt.Scan(&s2)
	count:=0
	for {
		index := strings.Index(s1,s2)
		if index == -1{
			break
		}
		s1 = s1[index+1:]
		count++
	}
	fmt.Println(count)
}