#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PRIM 1009//107374217

int mod (int a, int b) // reimplementare mod pentru ca in C nu merg bine operatiile modulo cu nr negative
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return mod(a, -b);
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

void potrivire_Rabin_Karp(char T[], char P[], int d)
{
    int n, m, q, h=1, i, p, t, s, ok, v[1000], pos=0;
    n= strlen(T);
    m= strlen(P);

    for(i=0;i<n;i++)
        T[i] = T[i] - '0';
    for(i=0;i<m;i++)
        P[i] = P[i] - '0';

    q = PRIM;
    h=1; // valoarea cea mai semnificativa dintr-o functie de m cifre
    for(i=0;i<m-1;i++)
        h=mod((h*d),q);

    p=0; // valoare numerica pt p
    t=0; // valoare numerica pt ts cu deplasament s=0

    for(i=0;i<m;i++)
    {
        p = mod((d*p + P[i]), q); //calculam valoarea numerica a sirului
        t = mod((d*t + T[i]), q); //calculam valoare numerica a sirului ts0
    }

    for(s=0;s<n-m+1;s++)
    {
        if(t == p)
        {
            //verificare false potriviri
            ok=1;
            for(i=0;i<m;i++)
                if(T[s+i]!=P[i])
                    {ok=0; break;}
            if(ok==1)
            {
                if(pos <1000)
                    v[pos++] = s;
                else
                    pos++;
            }

        }
        t = mod((d*(t-h*T[s]) + T[s+m]), q);
    }

    FILE *g = fopen("strmatch.out", "w");

    fprintf(g,"%d\n",pos);
    for(i=0;i<pos&& i<1000;i++)
        fprintf(g,"%d ",v[i]);

    fclose(g);

}

int main()
{
    int d;
    FILE *f;
    f = fopen("strmatch.in", "r");
    char *A, *B;

    A = (char*)malloc(2000001 *sizeof(char));
    B = (char*)malloc(2000001 *sizeof(char));

    fscanf(f,"%s", A);
    fscanf(f,"%s", B);
    fclose(f);

    d=26+26+10; //lungimea alfabetului

    potrivire_Rabin_Karp(B, A, d);

    return 0;
}