Cod sursa(job #1515662)

Utilizator herbertoHerbert Mohanu herberto Data 1 noiembrie 2015 23:38:24
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.78 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000001
#define MOD1 1000000007
#define MOD2 1000000021

char v1[MAXN], v2[MAXN];
int sol[MAXN];
int main(){
  FILE*fin=fopen("strmatch.in", "r");
  FILE*fout=fopen("strmatch.out", "w");
  int n1, n2, i, solutii;
  long long baza1, baza2, put1, put2, nr1, nr2, clar1, clar2;
  char c;
  c=fgetc(fin);
  n1=0;
  while(c!='\n'){
    n1++;
    v1[n1]=c;
    c=fgetc(fin);
  }
  c=fgetc(fin);
  n2=0;
  while(c!='\n' && c!=EOF){
    n2++;
    v2[n2]=c;
    c=fgetc(fin);
  }
  baza1=1;
  for(i=1; i<n1; i++){
    baza1*=123;
    baza1%=MOD1;
  }
  baza2=1;
  for(i=1; i<n1; i++){
    baza2*=123;
    baza2%=MOD2;
  }

  clar1=0;
  clar2=0;
  put1=1;
  put2=1;
  for(i=n1; i>=1; i--){
    clar1=clar1+v1[i]*put1;
    clar2=clar2+v1[i]*put2;
    clar1%=MOD1;
    clar2%=MOD2;
    put1*=123;
    put2*=123;
    put1%=MOD1;
    put2%=MOD2;
  }
//  printf("%lld %lld\n", clar1, clar2);

  nr1=0;
  nr2=0;
  put1=1;
  put2=1;
  for(i=n1; i>=1; i--){
    nr1=nr1+v2[i]*put1;
    nr2=nr2+v2[i]*put2;
    nr1%=MOD1;
    nr2%=MOD2;
    put1*=123;
    put2*=123;
    put1%=MOD1;
    put2%=MOD2;
  }
//    printf("%lld %lld\n", baza1, baza2);
//  printf("%lld", clar1);
  solutii=0;
  if(clar1==nr1 && clar2==nr2){
    solutii++;
    sol[solutii]=1;
  }
  for(i=2; i<=n2-n1+1; i++){
    nr1=nr1-v2[i-1]*baza1; nr1+=MOD1; nr1%=MOD1; nr1*=123; nr1+=v2[i+n1-1]; nr1%-MOD1;
    nr2=nr2-v2[i-1]*baza2; nr2+=MOD2; nr2%=MOD2; nr2*=123; nr2+=v2[i+n1-1]; nr2%=MOD2;
    if(clar1==nr1 && clar2==nr2){
      solutii++;
      sol[solutii]=i-1;
    }

//    printf("%d %lld %lld\n", i, nr1, nr2);
  }
  fprintf(fout, "%d\n", solutii);
  for(i=1; i<=solutii; i++)
    fprintf(fout, "%d ", sol[i]);
  return 0;
}