/*http://campion.edu.ro/arhiva/www/arhiva_2009/papers/paper8.pdf*/

#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>

#define DIM 2000005
#define d 62
#define q 100007

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char s[DIM], p[DIM];
vector <int> sol;

void det_functie(int &h, int exp){
    h=1;
    for(int i=1; i<=exp; i++)
        h = (h * d) % q;
}

void Rabin_Karp(char s[], char pattern[]){
    int n = strlen(s), m = strlen(pattern);
    int p=0, t=0, h;
    int contor = 0;
    det_functie(h,m-1);
    for(int i=0; i<m; i++){
        p = (d*p + pattern[i]) % q;
        t = (d*t + s[i]) % q;
    }
    for(int k=0; k <= n-m; k++){
        cout<<p<<" "<<t<<"\n";
        if(p == t)
            if(strncmp(s+k,pattern,m) == 0){
                contor++;
                if(contor <= 1000)
                    sol.push_back(k);
            }
        t = (d*(t - s[k]*h) + s[k+m]) % q;
        if(t<0)
            t += q;
    }
    g<<contor<<"\n";
}

void afisare(vector <int> v){
    int l = v.size();
    for(int i=0; i<l; i++)
        g<<v[i]<<" ";
}

int main()
{
    f>>p>>s;
    Rabin_Karp(s,p);
    afisare(sol);
}