字符串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;
}