//www.algorytm.org
//Algorytm KR (Karpa-Rabina) - wyszukiwanie wzorca
//(c)2006 Tomasz Lubiński

#include <stdio.h>
#include <string.h>

const r=256;   //liczba symboli alfabetu (char 0-255)
const q=9551;  //możliwie duża liczba pierwsza

// calculates a^b mod m
int power_modulo_fast(int a, int b, int m)
{
   int i;
   int result = 1;
   long int x = a%m;

   for (i=1; i<=b; i<<=1)
   {
      x %= m;
      if ((b&i) != 0)
      {
         result *= x;
         result %= m;
      }
      x *= x;
   }

   return result%m;
}

char wzorzec[1000];
char tekst[10000];
void main(void)
{
int m,n,i,j,h1,h2,rm;

printf("Podaj tekst\n");
scanf("%s",tekst);
printf("Podaj wzorzec\n");
scanf("%s",wzorzec);

n=strlen(tekst);
m=strlen(wzorzec);
h2=0; 
h1=0;
printf("Indeksy poczatkow wzorca w tekscie\n");

//algorytm Hornera do obliczenia funkcji haszujacej h(tekst[1..m])
for (i=0; i<m; i++)
{
   h2=((h2*r) + tekst[i]);
   h2%=q;
}
//algorytm Hornera do obliczenia funkcji haszujacej h(wzorzec)
for (i=0; i<m; i++)
{
   h1=((h1*r) + wzorzec[i]);
   h1%=q;
}

rm=power_modulo_fast(r, m-1, q);
i=0;
while (i<n-m)
{
	j=0;
	if (h1==h2) while ((j<m)&&(wzorzec[j]==tekst[i+j])) j++;
	if (j==m) printf("%d\n",i+1);
	h2=((h2-tekst[i]*rm)*r+tekst[i+m]);
        h2%=q;
        if (h2<0) h2+=q;
	i++;
}
j=0;
if (h1==h2) while ((j<m)&&(wzorzec[j]==tekst[i+j])) j++;
if (j==m) printf("%d\n",i+1);

return;
}