Pagini recente » Cod sursa (job #1845275) | Cod sursa (job #725797) | Cod sursa (job #2591186) | Cod sursa (job #980417) | Cod sursa (job #2067688)
#include <cstdio>
#define MOD1 100007
#define MOD2 100021
#define BAZA 73
using namespace std;
char a[2000001],b[2000001];
int ok[2000001];
int verif (int inc,int n){
int i,j=0;
for (i=inc;i-inc+1<=n;i++,j++)
if (a[j]!=b[i])
return 0;
return 1;
}
int main()
{
FILE *fin=fopen ("strmatch.in","r");
FILE *fout=fopen ("strmatch.out","w");
int n,m,sol,p1,p2,i;
int coda1,coda2,codb1,codb2;
char c;
c=fgetc (fin);
n=m=-1;
sol=0;
while (c!='\n'){
a[++n]=c;
c=fgetc (fin);
}
c=fgetc (fin);
while (c!='\n' && c!=EOF){
b[++m]=c;
c=fgetc (fin);
}
if (n>m){
fprintf (fout,"0");
return 0;
}
coda1=coda2=0;
p1=p2=1;
for (i=0;i<=n;i++){
coda1=( coda1 * BAZA + a[i])%MOD1;
coda2=( coda2 * BAZA + a[i])%MOD2;
if (i!=0){
p1=(p1*BAZA)%MOD1;
p2=(p2*BAZA)%MOD2;
}
}
codb1=codb2=0;
for (i=0;i<=n;i++){
codb1=(codb1*BAZA+b[i])%MOD1;
codb2=(codb2*BAZA+b[i])%MOD2;
}
if (codb1==coda1 && codb2==coda2)
ok[++sol]=0;
for (i=n+1;i<=m;i++){
//printf ("%d %d\n",codb1,codb2);
codb1=( ( codb1- ( b[i-n-1]*p1 ) %MOD1 + MOD1) * BAZA + b[i]) %MOD1;
codb2=( ( codb2- ( b[i-n-1]*p2 ) %MOD2 + MOD2) * BAZA + b[i]) %MOD2;
if (codb1==coda1 && codb2==coda2){
sol++;
ok[sol]=i-n;
}
}
fprintf (fout,"%d\n",sol);
for (i=1;i<=sol && i<=1000;i++)
fprintf (fout,"%d ",ok[i]);
return 0;
}