Cod sursa(job #1799032)

Utilizator andy1207Cioltan Andrei andy1207 Data 5 noiembrie 2016 17:57:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<cstdio>
#include<cstring>

char sir1[2000001];
char sir2[2000001];
int v[2000001];

int main()
{
 FILE *fin=fopen("strmatch.in","r");
 fscanf(fin,"%s",&sir1);
 fscanf(fin,"%s",&sir2);
 fclose(fin);
 int var=0,var1=0;
 char c;
 for(int i=0;i<strlen(sir1);i++)
    {
     if(sir1[i]>='A' && sir1[i]<='Z')
        c='A';
     else
        c='a'-'z'+'a'-1;
     var=(var*54+((sir1[i]-c+1)))%666013;
     var1=(var1*54+((sir1[i]-c+1)))%100003;
    }
 int verif=0,verif1=0,pdr541=1,pdr542=1;
 for(int i=0;i<strlen(sir1);i++)
    {
     if(sir2[i]>='A' && sir2[i]<='Z')
        c='A';
     else
        c='a'-'z'+'a'-1;
     verif=(verif*54+((sir2[i]-c+1)))%666013;
     verif1=(verif1*54+((sir2[i]-c+1)))%100003;
     if(i>=1)
        {
         pdr541=(pdr541*54)%666013;
         pdr542=(pdr542*54)%100003;
        }
    }
 int rez=0;
 if(verif==var && verif1==var1)
    {
     rez++;
     v[rez]=0;
    }
 for(int i=1;i<strlen(sir2)-strlen(sir1)+1;i++)
    {
     //verif=(verif-(sir2[i-1]-'A'+1)*pst27+(sir2[i+strlen(sir1)+1]-'A'+1)*pdr27);
     if(sir2[i-1]>='A' && sir2[i-1]<='Z')
        c='A';
     else
        c='a'-'z'+'a'-1;
     verif=((verif-(sir2[i-1]-c+1)*pdr541)*54+(sir2[i+strlen(sir1)-1]-c+1))%666013;
     verif1=((verif1-(sir2[i-1]-c+1)*pdr542)*54+(sir2[i+strlen(sir1)-1]-c+1))%100003;
     //pst27*=27;
     //pdr27*=27;
     if(verif==var && verif1==var1)
        {
         rez++;
         v[rez]=i;
        }
    }
 FILE *fout=fopen("strmatch.out","w");
 fprintf(fout,"%d\n",rez);
 if(rez>1000)
    rez=1000;
 for(int i=1;i<=rez;i++)
     fprintf(fout,"%d ",v[i]);
 fclose(fout);
 return 0;
}