Ham Z

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

string s,t;
int z[1500000];

void hamZ(const string &s)
{
    int n = s.size();
    z[0] = 0;
    int l = 0, r = 0;

    for (int i = 1; i < n; ++i)
    {
        if (r < i)
        {
            l = r = i;
            while (r < n && s[r-l] == s[r])
                ++r;
            z[i] = r-l; --r;
        }
        else{
            int k = i - l;
            if (z[k] < r-i+1)
                z[i] = z[k];
            else {
                l = i;
                while (s[r-l] == s[r]) ++r;
                z[i] = r-l; --r;
            }
        }
    }
}

int main()
{
    getline(cin,s);
    getline(cin,t);
    s = t + "#" + s;

    hamZ(s);

    for (int i = t.size()+1; i < s.size(); ++i)
        if (z[i] >= t.size())
            cout << i-t.size() << ' ';
    return 0;
}