Pagini recente » Cod sursa (job #1884654) | Cod sursa (job #1147936) | Cod sursa (job #3188319) | Monitorul de evaluare | Cod sursa (job #1255782)
//Solutie folosind Rabin-Karp
#include <cstdio>
#include <cstring>
using namespace std;
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013
char x[2000001],y[2000001];
int v1,v2,p1,p2,h1,h2,nr=0,v[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int n,m,i;
//citire
scanf("%s",&x);
scanf("%s",&y);
m=strlen(x);
n=strlen(y);
//daca primul sir e mai mare decat cel de-al doilea
if (m>n)
{
printf("0\n");
return 0;
}
p1=p2=1;
v1=v2=0;
for (i=0;i<m;i++)
{
v1=(v1*b1+x[i])%mod1;
v2=(v2*b2+x[i])%mod2;
if (i>=1)
{
p1=(p1*b1)%mod1;
p2=(p2*b2)%mod2;
}
}
h1=h2=0;
for (i=0;i<m;i++)
{
h1=(h1*b1+y[i])%mod1;
h2=(h2*b2+y[i])%mod2;
}
if (h1==v1&&h2==v2)
{
nr++;
v[nr]=0;
}
for (i=m;i<n;i++)
{
h1=((h1-(y[i-m]*p1)%mod1+mod1)*b1+y[i])%mod1;
h2=((h2-(y[i-m]*p2)%mod2+mod2)*b2+y[i])%mod2;
if (h1==v1&&h2==v2)
{
nr++;
v[nr]=i-m+1;
}
}
printf("%d\n",nr);
for (i=1;i<=nr && i<=1000;i++)
printf("%d ",v[i]);
return 0;
}