讲解

• 教程
  教程传送门

• 复杂度

1. 设主串为s，被查询串为t，长度分别为n、m
2. 预处理主串s的复杂度为O(n)
3. 预处理被查询串的复杂度为O(m)
4. 每次查询的复杂度为：O（n-m）

自然溢出代码（通过 unsigned 无符号数据类型 对数据溢出时自动 取余）

️自然溢出必须是无符号的数据类型否则的话一旦某个出现数据溢出，这个数就可能变成负数了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <stack>

#include <sstream>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define db double
#define Pir pair<int, int>
#define m_p make_pair
#define INF 0x3f3f3f3f
#define esp 1e-7
#define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
#define sc scanf
#define pr printf
#define sd(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
using namespace std;

#define mod (ll)(1e9 + 7)
const int mxn = 1e6 + 10;
char s[mxn], t[mxn];
ll hsh1[mxn];
ll hsh2[mxn];
ll pre[mxn];
ll hp = 131;

void get_hash(char s[], ll hash[], int n)
{
    for_(i, 1, n)
        hash[i] = hash[i - 1] * hp + s[i];
}

void init()
{
    pre[0] = 1;
    for_(i, 1, mxn - 1)
        pre[i] = pre[i - 1] * hp;
}

int main()
{
    
    init();
    int T; sd(T);
    while(T --)
    {
        ss(s + 1);
        ss(t + 1);
        int n = strlen(s + 1);
        int m = strlen(t + 1);
        get_hash(s, hsh1, n);
        get_hash(t, hsh2, m);
        
        int sum = 0;
        for_(i, n, m)
        {
            ll h = hsh2[i] - hsh2[i - n] * pre[n];
            if(h == hsh1[n]) sum ++;
        }
        pr("%d\n", sum);
    }

    return 0;
}

非自然溢出代码（取mod）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <stack>

#include <sstream>
void fre() { system("clear"), freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
void Fre() { system("clear"), freopen("A.txt", "r", stdin);}
#define ios ios::sync_with_stdio(false)
#define Pi acos(-1)
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define db double
#define Pir pair<int, int>
#define m_p make_pair
#define INF 0x3f3f3f3f
#define esp 1e-7
#define for_(i, s, e) for(int i = (ll)(s); i <= (ll)(e); i ++)
#define rep_(i, e, s) for(int i = (ll)(e); i >= (ll)(s); i --)
#define sc scanf
#define pr printf
#define sd(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
using namespace std;

#define mod (ll)(1e9 + 7)
const int mxn = 1e6 + 10;
char s[mxn], t[mxn];
ll hsh1[mxn];
ll hsh2[mxn];
ll pre[mxn];
ll hp = 131;

void get_hash(char s[], ll hash[], int n)
{
    for_(i, 1, n)
        hash[i] = (hash[i - 1] * hp + s[i]) % mod;
}

void init()
{
    pre[0] = 1;
    for_(i, 1, mxn - 1)
        pre[i] = pre[i - 1] * hp % mod;
}

int main()
{
    
    init();
    int T; sd(T);
    while(T --)
    {
        ss(s + 1);
        ss(t + 1);
        int n = strlen(s + 1);
        int m = strlen(t + 1);
        get_hash(s, hsh1, n);
        get_hash(t, hsh2, m);
        
        int sum = 0;
        for_(i, n, m)
        {
            int h = ((hsh2[i] - hsh2[i - n] * pre[n]) % mod + mod) % mod;
            if(h == hsh1[n]) sum ++;
        }
        pr("%d\n", sum);
    }

    return 0;
}

例题传送门