99. Поиск подстроки

/********************
* Problem:
* Theme:
*/
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(A) A.size()
#define f first
#define s second
#define endl '\n'

typedef vector<int> VI;
typedef vector<pair<int,int> > VII;
typedef vector<VI> VVI;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > pip;
typedef pair<pair<int,int>,pair<int,int> > ppp;
typedef pair<pair<int,int>,int> ppi;

const long double PI = acos(-1);
const int INF = 72340172838076673;
const int MOD = (int)1e9+7;
const int P = 3;
//const int N = 1e6+1;
const long double eps = 1e-8;

const int DX[] = {1,1,2,2,-1,-1,-2,-2};
const int DY[] = {-2,2,1,-1,-2,2,1,-1};

int bpow(int a,int b)
{
    if(b==0)
        return 1;
    if(b%2==0)
    {
        int t=bpow(a,b/2);
        return t*t;
    }
    return a*bpow(a,b-1);
}

bool isPrime(int n)
{
    if(n==1)
        return false;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

bool isPal(string s)
{
    if(s.size()==0)
        return false;
    for(int i=0,j=s.size()-1;i<j;i++,j--)
    {
        if(s[i]!=s[j])
            return false;
    }
    return true;
}

int amountOfDividers(int n)
{
    if(n==1)
        return 1;
    int counter=2 + (sqrt(n)==(int)sqrt(n));
    for(int i=2;i<sqrt(n);i++)
    {
        counter+=2*(n%i==0);
    }
    return counter;
}

int Hash[50001];
int PP[50001];
int N;

bool areEqual(int l,int r,int HASH)
{
    int K = Hash[r] - (l == 0 ? 0ll : Hash[l - 1]);
    while(K < 0)
        K+=MOD;
    K = (K * PP[N-l+1])%MOD;
    //cout << K << " " << HASH << " " << l << " " << r << "\n";
    return K == HASH;
}

void solve_case()
{
    string s;
    cin >> s;

    N = s.size();

    Hash[0] = s[0];

    PP[0] = 1;

    for(int i=1;i<s.size();i++)
    {
        PP[i] = (PP[i-1] * P)%MOD;
        Hash[i] = (Hash[i-1]+ s[i]*PP[i])%MOD;
    }

//    cout << "Hash array : ";
//
//    for(int i=0;i<s.size();i++)
//    {
//        cout << Hash[i] << " ";
//    }
//
//    cout << "\n";

    string ss;
    cin >> ss;

    if(ss.size() > s.size())
        return;

    int HASH = ss[0];

    for(int i=1;i<ss.size();i++)
    {
        PP[i] = (PP[i-1] * P)%MOD;
        HASH = (HASH + ss[i]*PP[i])%MOD;
    }

    PP[N] = PP[N-1]*P;
    PP[N+1] = PP[N]*P;

    HASH = (HASH * PP[N+1])%MOD;

    //cout << HASH << "\n";

    for(int i=0;i<=s.size()-ss.size();i++)
    {
        if(areEqual(i,i+ss.size()-1,HASH))
            cout << i << " ";
    }

    return;
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int t=1;
    //cin >> t;

    while(t--)
    {
        solve_case();
    }

    return 0;
}