Mai intai trebuie sa te autentifici.
Cod sursa(job #1982348)
Utilizator | Data | 18 mai 2017 14:49:10 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.36 kb |
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int s1,s2,n,m,i,k,p62[3];
int v[2000001],a[2000001],b[2000001];
char sir1[2000001],sir2[2000001];
int functie(int MOD,int s,int indice){
int x;
x=(b[i-n]*p62[indice])%MOD;
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,l;
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;
}
*/
for(i=0;i<n;i++){
if(sir1[i]>='a'&&sir1[i]<='z')
a[i+1]=sir1[i]-'a'+10;
if(sir1[i]>='A'&&sir1[i]<='Z')
a[i+1]=sir1[i]-'A'+36;
if(sir1[i]>='0'&&sir1[i]<='9')
a[i+1]=sir1[i]-'0';
}
m=strlen(sir2);
for(i=0;i<m;i++){
if(sir2[i]>='a'&&sir2[i]<='z')
b[i+1]=sir2[i]-'a'+10;
if(sir2[i]>='A'&&sir2[i]<='Z')
b[i+1]=sir2[i]-'A'+36;
if(sir2[i]>='0'&&sir2[i]<='9')
b[i+1]=sir2[i]-'0';
}
MOD=666013;
ref1=0;
p=1;
for(i=n;i>=1;i--){
ref1=(ref1+p*a[i])%MOD;
p=p*62%MOD;
}
MOD=1000003;
ref2=0;
p=1;
for(i=n;i>=1;i--){
ref2=(ref2+p*a[i])%MOD;
p=p*62%MOD;
}
MOD=666013;
s1=0;
p=1;
for(i=n;i>=1;i--){
s1=(s1+(p*b[i])%MOD)%MOD;
p=p*62%MOD;
}
MOD=1000003;
s2=0;
p=1;
for(i=n;i>=1;i--){
s2=(s2+(p*b[i])%MOD)%MOD;
p=p*62%MOD;
}
k=0;
if(s1==ref1&&s2==ref2){
k++;
v[k]=0;
}
p62[1]=1;
for(l=1;l<n;l++)
p62[1]=p62[1]*62%666013;
p62[2]=1;
for(l=1;l<n;l++)
p62[2]=p62[2]*62%1000003;
for(i=n+1;i<=m;i++){
s1=functie(666013,s1,1);
s2=functie(1000003,s2,2);
if(s1==ref1&&s2==ref2){
k++;
v[k]=i-n;
}
}
fprintf(fout,"%d\n",k);
for(i=1;i<=k&&i<=1000;i++)
fprintf(fout,"%d ",v[i]);
fclose(fin);
fclose(fout);
return 0;
}