Pagini recente » Cod sursa (job #3179119) | Cod sursa (job #1714742) | Cod sursa (job #2163480) | Cod sursa (job #845009) | Cod sursa (job #622504)
Cod sursa(job #622504)
#include <stdio.h>
#include <string.h>
#define dim 2000001
#define p 101
#define m1 100007
#define m2 100021
char a[dim],b[dim];
int n,m,t,c[dim];
int ha1,ha2,hb1,hb2;
inline int match()
{
if ((ha1==hb1)&&(ha2==hb2))
{
t ++;
return 1;
}
return 0;
}
void rabin_karp()
{
int i,mp1=1,mp2=1;
if (n>=m)
{
for (i=0;i<m;i++)
{
ha1=(ha1 * p + a[i])%m1;
ha2=(ha2 * p + a[i])%m2;
hb1 = (hb1 * p + b[i])%m1;
hb2 = (hb2 * p + b[i])%m2;
if (i!=0)
{
mp1 = (mp1 * p)%m1; //max power modulo m1 at end of i
mp2 = (mp2 * p)%m2; //max power modulo m2 at end of i
}
}
c[0]=match(); //check for the first string
for (i=1;i<=n-m;i++)
{
ha1=((ha1-(a[i-1]*mp1)%m1 + m1)*p + a[i+m-1])%m1;
ha2=((ha2-(a[i-1]*mp2)%m2 + m2)*p + a[i+m-1])%m2;
c[i]=match();
}
}
}
int main()
{
int i,j;
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf("%s",b);
scanf("%s",a);
n = strlen(a);
m = strlen(b);
rabin_karp();
printf("%d\n",t);
for (i=0,j=0;(j<t)&&(j<1000)&&(i<=n-m);i++)
{
if (c[i]==1)
{
printf("%d ",i);
j++;
}
}
return 0;
}