Pagini recente » Cod sursa (job #791766) | Cod sursa (job #2436447) | Cod sursa (job #2764490) | Cod sursa (job #2428754) | Cod sursa (job #2418798)
#include <cstdio>
#include <cstring>
#define MOD1 666013
#define MOD2 1000003
char a[2000001],b[2000001];
int v[1001];
int main(){
FILE* fin=fopen("strmatch.in","r");
FILE* fout=fopen("strmatch.out","w");
int nra1=0,nra2=0,nrb1=0,nrb2=0,nr=0,n1,n2,i,x1=1,x2=1,nr1,nr2;
fscanf (fin,"%s %s",&a,&b);
n1=strlen(a);
n2=strlen(b);
for (i=0;i<n1;i++){
if (a[i]>='0' && a[i]<='9')
nr1=a[i]-'0';
if (b[i]>='0' && b[i]<='9')
nr2=b[i]-'0';
if (a[i]>='a' && a[i]<='z')
nr1=a[i]-'a'+10;
if (b[i]>='a' && b[i]<='z')
nr2=b[i]-'a'+10;
if (a[i]>='A' && a[i]<='Z')
nr1=a[i]-'A'+36;
if (b[i]>='A' && b[i]<='Z')
nr2=b[i]-'A'+36;
nra1=(nra1*62+nr1)%MOD1;
nra2=(nra2*62+nr1)%MOD2;
nrb1=(nrb1*62+nr2)%MOD1;
nrb2=(nrb2*62+nr2)%MOD2;
if (i){
x1=(x1*62)%MOD1;
x2=(x2*62)%MOD2;
}
}
for (i=n1;i<n2;i++){
if (nra1==nrb1 && nra2==nrb2){
nr++;
if (nr<=1000)
v[nr]=i-n1;
}
if (b[i-n1]>='0' && b[i-n1]<='9')
nr1=b[i-n1]-'0';
if (b[i]>='0' && b[i]<='9')
nr2=b[i]-'0';
if (b[i-n1]>='a' && b[i-n1]<='z')
nr1=b[i-n1]-'a'+10;
if (b[i]>='a' && b[i]<='z')
nr2=b[i]-'a'+10;
if (b[i-n1]>='A' && b[i-n1]<='Z')
nr1=b[i-n1]-'A'+36;
if (b[i]>='A' && b[i]<='Z')
nr2=b[i]-'A'+36;
nrb1=((((nrb1-(nr1*x1)%MOD1+MOD1)%MOD1)*62)%MOD1+nr2)%MOD1;
nrb2=((((nrb2-(nr1*x2)%MOD2+MOD2)%MOD2)*62)%MOD2+nr2)%MOD2;
}
if (nra1==nrb1 && nra2==nrb2){
nr++;
if (nr<=1000)
v[nr]=n2-n1;
}
fprintf (fout,"%d\n",nr);
if (nr>1000)
nr=1000;
for (i=1;i<=nr;i++)
fprintf (fout,"%d ",v[i]);
return 0;
}