Cod sursa(job #594980)

Utilizator Smaug-Andrei C. Smaug- Data 10 iunie 2011 18:11:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>

#define MAXN 2000001

#define MOD1 100007
#define MOD2 100021
#define BS 73

int main(){

  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  int NA, NB, hA1, hA2, hB1, hB2, B1, B2, c, i;
  char A[MAXN], B[MAXN];
  bool match[MAXN];
  
  scanf("%s %s", A, B);
  NA=strlen(A);
  NB=strlen(B);

  if(NA > NB){
    printf("0\n");
    return 0;
  }

  B1=B2=1;
  hA1=hA2=0;
  for(i=0; i<NA; i++){
    hA1=(hA1*BS+A[i])%MOD1;
    hA2=(hA2*BS+A[i])%MOD2;
    if(i){
      B1=(B1*BS)%MOD1;
      B2=(B2*BS)%MOD2;
    }
  }
  
  hB1=hB2=0;
  for(i=0; i<NA; i++){
    hB1=(hB1*BS+B[i])%MOD1;
    hB2=(hB2*BS+B[i])%MOD2;
  }
  
  c=0;
  if(hA1==hB1 && hA2==hB2){
    match[0]=true; c++;
  }

  for(i=NA; i<NB; i++){
    hB1=((hB1-(B[i-NA]*B1)%MOD1+MOD1)*BS+B[i])%MOD1;
    hB2=((hB2-(B[i-NA]*B2)%MOD2+MOD2)*BS+B[i])%MOD2;

    if(hA1==hB1 && hA2==hB2){
      match[i-NA+1]=true; c++;
    }
  }
  printf("%d\n", c);
  
  c=0;
  for(i=0; i<NB && c<1000; i++)
    if(match[i]){
      printf("%d ", i); c++;
    }
  
  printf("\n");
  
  return 0;
  
}