#if 0

#if 0

#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

#define notlocal 0

#if !notlocal

#include <iostream>
#define fin std::cin
#define fout std::cout

#else

#include <fstream>
std::ifstream fin("cernobil.in");
std::ofstream fout("cernobil.out");

#endif

using namespace std;

const int NMAX = 105;

int n, m, r;
int dx[] = { -1, 0, 1,  0};
int dy[] = {  0, 1, 0, -1};

int mat[NMAX][NMAX];
int viz[NMAX][NMAX];
int cost[NMAX][NMAX][NMAX];

struct poz
{
    int x, y;
};

bool inb(int x, int y)
{
    return 0 < x && x <= n && 0 < y && y <= m;
}

bool inb(poz lmao)
{
    return inb(lmao.x, lmao.y);
}

struct MUCHIE
{
    poz pozitie;
    int cost;
    int radiatie;
};

bool operator<(const MUCHIE& a, const MUCHIE& b)
{
    if (a.cost == b.cost)
    {
        return a.radiatie > b.radiatie;
    }
    return a.cost > b.cost;
}

void Dijkstra(poz start)
{
    memset(cost, 0b01111111, sizeof(cost));
    priority_queue <MUCHIE> pq;
    MUCHIE m, vecin;
    pq.push({start, 0, 0});
    cost[start.x][start.y][0] = 0;
    while (!pq.empty())
    {
        m = pq.top();
        pq.pop();
        for (int k = 0; k < 4; ++k)
        {
            vecin.pozitie.x = m.pozitie.x + dx[k];
            vecin.pozitie.y = m.pozitie.y + dy[k];
            if (inb(vecin.pozitie))
            {
                vecin.cost = 1;
                vecin.radiatie = m.radiatie + mat[vecin.pozitie.x][vecin.pozitie.y];
                if (vecin.radiatie <= r)
                {
                    if (cost[vecin.pozitie.x][vecin.pozitie.y][vecin.radiatie] > cost[m.pozitie.x][m.pozitie.y][m.radiatie] + vecin.cost)
                    {
                        cost[vecin.pozitie.x][vecin.pozitie.y][vecin.radiatie] = cost[m.pozitie.x][m.pozitie.y][m.radiatie] + vecin.cost;
                        pq.push({vecin.pozitie, 1, vecin.radiatie});
                    }
                }
            }
        }
    }
}

void reconstruire(int radiat)
{
    stack <poz> st;
    poz finalul;
    finalul.x = n;
    finalul.y = m;
    poz vecin;
    int costul = cost[finalul.x][finalul.y][radiat];
    int rad = radiat;
    st.push(finalul);
    bool ok;
    while (costul)
    {
        --costul;
        rad -= mat[finalul.x][finalul.y];
        ///ok = 1;
        for (int k = 0; k < 4; ++k)
        {
            vecin.x = finalul.x + dx[k];
            vecin.y = finalul.y + dy[k];
            if (inb(vecin))
            {
                if (cost[vecin.x][vecin.y][rad] == costul)
                {
                    st.push(vecin);
                    ///ok = 0;
                    finalul = vecin;
                    break;
                }
            }
        }
    }
    while (!st.empty())
    {
        fout << st.top().x << ' ' << st.top().y << '\n';
        st.pop();
    }
}

void completare(int xc, int yc, int p)
{
    for (int i = max(1, xc - p); i <= min(n, xc + p); ++i)
    {
        for (int j = max(1, yc - p); j <= min(m, yc + p); ++j)
        {
            mat[i][j] += max(0, p - abs(xc - i) - abs(yc - j));
        }
    }
}

int main()
{
    int k;
    fin >> n >> m >> k >> r;
    int x, y, p;
    for (int i = 0; i < k; ++i)
    {
        fin >> x >> y >> p;
        completare(x, y, p);
    }
    Dijkstra({1, 1});
    int mini = cost[n][m][0], rad_drummin = 0;
    for (int k = 1; k <= r; ++k)
    {
        if (mini > cost[n][m][k])
        {
            mini = cost[n][m][k];
            rad_drummin = k;
        }
    }
    fout << mini + 1 << '\n';
    reconstruire(rad_drummin);
    return 0;
}

/**
8 8 3 1
3 2 3
3 5 2
6 7 2
*/

#endif

#include <vector>
#include <queue>
#include <cstring>

#define notlocal 69

#if !notlocal

#include <iostream>
#define fin std::cin
#define fout std::cout

#else

#include <fstream>
std::ifstream fin("dijkstrain.txt");
std::ofstream fout("dijkstraout.txt");

#endif

using namespace std;

const int NMAX = 50000;

struct MUCHIE
{
    int nod, cost;
};

bool operator<(const MUCHIE& a, const MUCHIE& b)
{
    if (a.cost == b.cost)
    {
        return a.nod > b.nod;
    }
    return a.cost > b.cost;
}

std::vector <MUCHIE>G[NMAX + 5];
int n, viz[NMAX + 5], cost[NMAX + 5], t[NMAX + 5];

std::ostream& operator<<(std::ostream& stream, const int* const ptr)
{
    for (int i = 1; i <= n; ++i)
    {
        stream << *(ptr + i) << ' ';
    }
    return stream;
}

void Dijkstra(int start)
{
    memset(cost, 0b01111111, sizeof(cost));
    fout << "Initializam vectorul ce retine distanta minima de la nodul de start la fiecare nod(vom nota cu cost[i] distanta minima): " << start << " cu " << 0b01111111011111110111111101111111 << ". Acest numar este pe postul lui infinit si este un numar care ar trebui sa fie mai mare decat distanta maxima de la nodul de start la toate nodurile. Daca pentru un numar i valoarea din vector la pozitia i este tot infinit inseamna ca nu exista drum de la nodul de start la nodul i\n";
    fout << "Vom retine in vectorul viz, in viz[i], 0 daca nodul i nu a fost vizitat si 1 daca nodul i a fost vizitat";
    fout << "Vom retine in vectorul t vectorul de \"tati\" de care ne vom folosi pentru reconstruirea drumurilor\n";
    cost[start] = 0;
    fout << "Vectorii:\n";
    fout << "cost: " << cost << '\n';
    fout << "viz: " << viz << '\n';
    fout << "t: " << t << '\n';
    fout << '\n';
    MUCHIE m;
    std::priority_queue <MUCHIE> pq;
    pq.push({start, 0});
    ///t[start] = 0;
    while (!pq.empty())
    {
        while (!pq.empty() && viz[pq.top().nod])
        {
            pq.pop();
            fout << "In nodul " << pq.top().nod << " s-a ajuns cu costul " << pq.top().cost << " insa s-a putut ajunge cu un cost mai bun, acela fiind " << cost[pq.top().nod] << '\n';
        }
        if (pq.empty())
        {
            break;
        }
        m = pq.top();
        pq.pop();
        viz[m.nod] = 1;
        fout << "Continuam parcurgerea pe nodul cu distanta cea mai mica fata de nodul de start, acela fiind " << m.nod << '\n';
        fout << "Vectorii dupa actualizare:\n";
        fout << "cost: " << cost << '\n';
        fout << "viz: " << viz << '\n';
        fout << "t: " << t << '\n';
        fout << '\n';
        fout << "Parcurgem vecinii nodului " << m.nod << '\n';
        for (MUCHIE it : G[m.nod])
        {
            if (!viz[it.nod] && cost[it.nod] > m.cost + it.cost)
            {
                fout << "Inainte de vizitare distanta pana la " << it.nod << " era " << cost[it.nod] << ". Dupa actualizare acesta va fi " << m.cost + it.cost << "\n";
                cost[it.nod] = m.cost + it.cost;
                t[it.nod] = m.nod;
                pq.push({it.nod, cost[it.nod]});
                fout << "Vectorii dupa actualizare:\n";
                fout << "cost: " << cost << '\n';
                fout << "viz: " << viz << '\n';
                fout << "t: " << t << '\n';
                fout << '\n';
            }
            if (!viz[it.nod] && cost[it.nod] <= m.cost + it.cost)
            {
                fout << "In nodul " << it.nod << " nu are rost sa actualizam deoarece s-a putut ajunge cu un cost mai mic sau egal\n";
            }
        }
        fout << "Am terminat parcurgerea vecinilor nodului " << m.nod << "\n\n";
    }
    fout << "Algoritmul lui Dijkstra s-a executat cu succes\n";
}

void drum(int x)
{
    if (t[x])
    {
        drum(t[x]);
    }
    fout << x << ' ';
}

int main()
{
    int m, x, y, z;
    fin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
        ///G[y].push_back({x, z});
    }
    Dijkstra(1);
    fout << "Acum vom afisa vectorul cost. Daca valoarea lui v[i] este mai mica decat " << 0b01111111011111110111111101111111 << " inseamna ca aceea este distanta minima de a ajunge de la nodul de start in nodul i, altfel inseamna ca nu exista drum de la nodul de start la nodul i\n";
    fout << "cost: " << cost << "\n";
    fout << "Acum vom reconstrui drumul folosind vectorul de tati:\n";
    for (int i = 1; i <= n; ++i)
    {
        fout << "Pentru nodul " << i << " avem drumul: ";
        drum(i);
        fout << "\n";
    }
    return 0;
}

#endif

#if 0

#include <vector>
#include <queue>
#include <cstring>

#define notlocal 1

#if !notlocal

#include <iostream>
#define fin std::cin
#define fout std::cout

#else

#include <fstream>
std::ifstream fin("aib.in");
std::ofstream fout("aib.out");

#endif

using namespace std;

const int NMAX = 1e5;
int v[NMAX + 5], n;

void update(int val, int poz)
{
    while (poz <= n)
    {
        v[poz] += val;
        poz += (poz & (-poz));
    }
}

int query(int poz)
{
    int sum = 0;
    while (poz)
    {
        sum += v[poz];
        poz -= (poz & (-poz));
    }
    return sum;
}

int bs(int val)
{
    int cval = val;
    int pas = 1 << 20;
    int r = 0;
    while (pas)
    {
        if (r + pas <= n && v[r + pas] < val)
        {
            r += pas;
            val -= v[r];
        }
        pas >>= 1;
    }
    if (query(r + 1) == cval)
    {
        return r + 1;
    }
    else
    {
        return -1;
    }
}

int main()
{
    int a, b, x;
    int m;
    int idk;
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        fin >> x;
        update(x, i);
    }
    while (m--)
    {
        fin >> idk;
        if (idk == 0)
        {
            fin >> a >> b;
            update(b, a);
        }
        else if (idk == 1)
        {
            fin >> a >> b;
            fout << query(b) - query(a - 1) << '\n';
        }
        else
        {
            fin >> a;
            fout << bs(a) << '\n';
        }
    }
    return 0;
}
#endif

#include <vector>
#include <string>

#define notlocal 1

#if !notlocal

#include <iostream>
#define fin std::cin
#define fout std::cout

#else

#include <fstream>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

#endif

using namespace std;

const int NMAX = 2e6;

const int hashbase = 256;
const int mod = 101;

vector <int> poz;

int hashadd(int currenthash, int charnew)
{
    return (currenthash * hashbase + charnew) % mod;
}

int hashsub(int currenthash, int charold, int coef)
{
    return ((currenthash - charold * coef) % mod + mod) % mod;
}

int main()
{
    int i;
    int hasha = 0, hashb = 0, coef = 1;
    string a, b;
    fin >> a >> b;
    if (b.size() < a.size())
    {
        fout << 0;
        return 0;
    }
    for (i = 0; i < a.size(); ++i)
    {
        hasha = hashadd(hasha, a[i]);
        hashb = hashadd(hashb, b[i]);
        coef = (coef * hashbase) % mod;
    }
    if (hasha == hashb && b.compare(0, a.size(), a) == 0)
    {
        poz.push_back(0);
    }
    for (; i < b.size(); ++i)
    {
        hashb = hashadd(hashb, b[i]);
        hashb = hashsub(hashb, b[i - a.size()], coef);
        if (hasha == hashb && b.compare(i - a.size() + 1, a.size(), a) == 0)
        {
            poz.push_back(i - a.size() + 1);
        }
    }
    fout << poz.size() << '\n';
    for (auto it : poz)
    {
        fout << it << ' ';
    }
    return 0;
}