Pagini recente » Cod sursa (job #1891889) | Cod sursa (job #734933) | Cod sursa (job #539025) | Cod sursa (job #2799890) | Cod sursa (job #1513850)
#include <stdio.h>
#include <string.h>
#define N1 100007
#define N2 100021
char s1[2000001], s2[2000001];
int Ns1, Ns2;
int nrs1, nrs2, p1, p2;
char v[2000001];
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s",&s1,&s2);
Ns1=strlen(s1);
Ns2=strlen(s2);
p1=p2=1;
nrs1=nrs2=0;
for (int i=0;i<Ns1;i++){
nrs1=(nrs1*73+s1[i])% N1;
nrs2=(nrs2*73+s1[i])% N2;
if (i!=0)
p1=(p1*73)% N1,
p2=(p2*73)%N2;
}
if (Ns1>Ns2){
printf("0\n");
}
else{
int nr1=0,nr2=0;
for (int i=0;i<Ns1;i++){
nr1=(nr1*73+s2[i])%N1;
nr2=(nr2*73+s2[i])%N2;
}
int k=0;
if (nr1==nrs1&&nr2==nrs2){
v[0]=1;
k++;
}
for (int i=Ns1;i<Ns2;i++){
nr1=((nr1-(s2[i-Ns1]*p1)%N1+N1)*73+s2[i])%N1;
nr2=((nr2-(s2[i-Ns1]*p2)%N2+N2)*73+s2[i])%N2;
if (nr1==nrs1&&nr2==nrs2){
v[i-Ns1+1]=1;
k++;
}
}
printf("%d\n",k);
k = 0;
for (int i=0;i<Ns2&&k<1000;i++)
if(v[i]==1){
k++;
printf("%d ",i);
}
printf("\n");
}
return 0;
}