算法

(字符串哈希) $O(m)$

预处理哈希值 对长串进行扫描

时间复杂度

分别预处理p串和s串的哈希值：复杂度为O(n+m)
遍历一遍S串进行匹配 O（m） 实际只需要遍历到m-n+1位 ：复杂度为O(m-n+1)
总体复杂度为O(m)

C++ 代码

//字母不能映射成0
//  A->0
//  AA->00 
//  p=131或13331  Q=2^64  99.9%不会冲突 
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+10,P=131;

int n,m;
char str1[N],str2[N];
ull h1[N],p1[N];
ull h2[N],p2[N];
//子串L-R的哈希值为   R的哈希值-(L-1)的哈希值*P^(R-L+1) 

ull get1(int l,int r)
{
    return h1[r]-h1[l-1]*p1[r-l+1];    
}
ull get2(int l,int r)
{
    return h2[r]-h2[l-1]*p2[r-l+1];
}
int main()
{
    cin>>n>>str1+1>>m>>str2+1;
    p1[0]=1;p2[0]=1;
    for(int i=1;i<=n;i++)
    {
        p1[i]=p1[i-1]*P;
        h1[i]=h1[i-1]*P+str1[i];  //预处理子串哈希值
    }
    for(int i=1;i<=m;i++)
    {
        p2[i]=p2[i-1]*P;
        h2[i]=h2[i-1]*P+str2[i]; // 预处理母串哈希值
    }
    for(int i=1;i<=m-n+1;i++)    // 把整个子串和哈希值沿着母串逐次匹配
    {
        if(get1(1,n)==get2(i,i+n-1)) cout<<i-1<<" ";
    }

    return 0;
}