Pagini recente » Cod sursa (job #589117) | Cod sursa (job #1333051) | Cod sursa (job #84138) | Cod sursa (job #1991722) | Cod sursa (job #1982167)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int s1,s2,n,m,i,k;
int v[2000001],a[2000001],b[2000001];
char sir1[2000001],sir2[2000001];
int functie(int MOD,int s){
int l,p62,x;
p62=1;
for(l=1;l<n;l++)
p62=p62*62%MOD;
x=b[i-n]*p62;
x=(s+MOD-x)%MOD;
x=(x*62+b[i])%MOD;
return x;
}
int main(){
FILE *fin,*fout;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
int MOD,ref1,ref2,p;
fscanf(fin,"%s%s",sir1,sir2);
n=strlen(sir1);
for(i=0;i<n;i++){
if(sir1[i]>='a'&&sir1[i]<='z')
a[i+1]=sir1[i]-'a'+26;
if(sir1[i]>='A'&&sir1[i]<='Z')
a[i+1]=sir1[i]-'A';
if(sir1[i]>='0'&&sir1[i]<='9')
a[i+1]=sir1[i]-'0'+52;
}
m=strlen(sir2);
for(i=0;i<m;i++){
if(sir2[i]>='a'&&sir2[i]<='z')
b[i+1]=sir2[i]-'a'+26;
if(sir2[i]>='A'&&sir2[i]<='Z')
b[i+1]=sir2[i]-'A';
if(sir2[i]>='0'&&sir2[i]<='9')
b[i+1]=sir2[i]-'0'+52;
}
MOD=666013;
ref1=0;
p=1;
for(i=n;i>=1;i--){
ref1=(ref1+p*a[i])%MOD;
p*=62;
}
MOD=1000003;
ref2=0;
p=1;
for(i=n;i>=1;i--){
ref2=(ref2+p*a[i])%MOD;
p*=62;
}
MOD=666013;
s1=0;
p=1;
for(i=n;i>=1;i--){
s1=(s1+p*b[i])%MOD;
p*=62;
}
MOD=1000003;
s2=0;
p=1;
for(i=n;i>=1;i--){
s2=(s2+p*b[i])%MOD;
p*=62;
}
k=0;
if(s1==ref1&&s2==ref2){
k++;
v[k]=1;
}
for(i=n+1;i<=m;i++){
s1=functie(666013,s1);
s2=functie(1000003,s2);
if(s1==ref1&&s2==ref2){
k++;
v[k]=i-n;
}
}
fprintf(fout,"%d\n",k);
for(i=1;i<=k;i++)
fprintf(fout,"%d ",v[i]);
fclose(fin);
fclose(fout);
return 0;
}