Cod sursa(job #2537045)

Utilizator andra1782Andra Alazaroaie andra1782 Data 2 februarie 2020 22:29:47
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <string.h>
#define S 63
#define MAX 2000000
#define MOD1 666013
#define MOD2 1000000007
char a[MAX],b[MAX];

char conv(char x){
  if('0'<=x && x<='9')
    x-='0';
  else if('a'<=x && x<='z')
    x=x-'a'+10;
  else
    x=x-'A'+36;
  return x;
}

int v[MAX];
int main(){
  FILE *fin=fopen("strmatch.in","r");
  FILE *fout=fopen("strmatch.out","w");
  int n,m,i,am1,am2,bm1,bm2,p1,p2,sol=0;

  fscanf(fin,"%s",&a);
  fscanf(fin,"%s",&b);
  n=strlen(a);
  m=strlen(b);
  if(n>m)
    sol=0;
  else{
    am1=am2=bm1=bm2=0;
    p1=p2=1;
    for(i=0; i<n; i++){
      a[i]=conv(a[i]);
      b[i]=conv(b[i]);
      am1=(am1*S+a[i])%MOD1;
      am2=(am2*S+a[i])%MOD2;
      bm1=(bm1*S+b[i])%MOD1;
      bm2=(bm2*S+b[i])%MOD2;
      p1=(p1*S)%MOD1;
      p2=(p2*S)%MOD2;
    }
    p1/=S;
    p2/=S;
    for(i=n; i<m; i++){
      b[i]=conv(b[i]);
      bm1=((bm1-b[i-n]*p1)*S+b[i]+MOD1)%MOD1;
      bm2=((bm2-b[i-n]*p2)*S+b[i]+MOD2)%MOD2;
      if(am1==bm1 && am2==bm2)
        v[sol++]=i-n+1;
    }
  }
  fprintf(fout,"%d\n",sol);
  for(i=0; i<sol; i++)
    fprintf(fout,"%d ",v[i]);
  fclose(fin);
  fclose(fout);
  return 0;
}