C++14(g++5.4) 解法, 执行用时: 901ms, 内存消耗: 11580K, 提交时间: 2019-12-12 19:19:59

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

const int MAXN = 1e6+300;
const int P = 1e9+7;
int H[MAXN];
int B[MAXN];
string s;
int gao(string &w) {
  int cnt = 0;
  int h = 0; for (auto c: w) h = h * P + c;
  for (int i = 0; i < s.size(); i++) {
    H[i+1] = H[i] * P + s[i];
    int j = i - int(w.size());
    if (j >= 0) {
      H[i+1] -= s[j] * B[w.size()];
    }
    if (H[i+1] == h) cnt++;
  }
  return cnt;
}
int main() {
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<string> words(N); for (auto &w: words) cin >> w;
  for (auto &w: words) s.append("#"), s.append(w);
  // for (int i = 0; i < s.size(); i++) H[i+1] = H[i] * P + s[i];
  B[0] = 1;
  for (int i = 0; i < s.size(); i++) B[i+1] = B[i] * P;

  for (auto &w: words) cout << gao(w) << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 501ms, 内存消耗: 10484K, 提交时间: 2020-03-05 14:29:54

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+300;
const int P=1e9+7;
int H[MAXN];
int B[MAXN];
string s;
int gao(string &w)
{
	int cnt=0;
	int h=0;
	for(auto c:w) h=h*P+c;
	for(int i=0;i<s.size();i++)
	{
		H[i+1]=H[i]*P+s[i];
		int j=i-int(w.size());
		if(j>=0)
		{
			H[i+1]-=s[j]*B[w.size()];
			
		}
		if(H[i+1]==h) cnt++;
	}
	return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	int N;
	cin>>N;
	vector<string> words(N);
	for(auto &w:words) cin>>w;
	for(auto &w:words) s.append("#"),s.append(w);
	B[0]=1;
	for(int i=0;i<s.size();i++) B[i+1]=B[i]*P;
	for(auto &w:words) cout<<gao(w)<<endl;
}