Pagini recente » Cod sursa (job #2478836) | Cod sursa (job #342586) | Cod sursa (job #590383) | Cod sursa (job #2745299) | Cod sursa (job #1252782)
/*
Rabin-Karp
#include<cstdio>
#include<cstring>
using namespace std;
#define m1 100007
#define m2 100021
int n,m,i,a1,a2,k,p1,p2,b1,b2,c[2000001];
char a[2000001],b[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a)-1;
m=strlen(b)-1;
if(n>m)
{
printf("0");
return 0;
}
for(i=0;i<=n;i++)
{
a1=(a1*73+a[i])%m1;
a2=(a2*73+a[i])%m2;
}
p1=1;
p2=1;
for(i=0;i<=n;i++)
{
b1=(b1*73+b[i])%m1;
b2=(b2*73+b[i])%m2;
if(i>0)
{
p1=(p1*73)%m1;
p2=(p2*73)%m2;
}
}
if(a1==b1&&a2==b2)k++,c[k]=0;
for(i=n+1;i<=m;i++)
{
b1=((b1-(b[i-n-1]*p1)%m1+m1)*73+b[i])%m1;
b2=((b2-(b[i-n-1]*p2)%m2+m2)*73+b[i])%m2;
if(a1==b1&&a2==b2)k++,c[k]=i-n;
}
printf("%d\n",k);
if(k>1000)k=1000;
for(i=1;i<=k;i++)
printf("%d ",c[i]);
return 0;
}*/
// KMP
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,j,k,q,d[2000002],p[2000002];
char x[2000002],y[2000002];
void constructie_pi()
{
int k,i;
k=0;
p[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&x[k+1]!=x[i])
k=p[k];
if(x[i]==x[k+1])k++;
p[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(x+1);
gets(y+1);
x[0]=' ';
y[0]=' ';
n=strlen(x)-1;
m=strlen(y)-1;
constructie_pi();
k=0;
p[1]=0;
for(i=1;i<=m;i++)
{
while(k>0&&x[k+1]!=y[i])
k=d[k];
if(y[i]==x[k+1])k++;
d[i]=k;
}
for(i=1;i<=m;i++)
if(d[i]==n)q++;
printf("%d\n",q);
q=0;
for(i=n;i<=m;i++)
if(d[i]==n)
{
printf("%d ",i-n);
q++;
if(q==1000)break;
}
return 0;
}