Cod sursa(job #3369475)

Utilizator maria.bertolonMaria Bertolon maria.bertolon Data 20 octombrie 2026 16:53:46
Problema Potrivirea sirurilor Scor 14
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MOD 1000000007
#define BAZA 67
#define MAXN 2000000

char a[MAXN], b[MAXN];
char val['z' + 1];
int ans[MAXN];

void init(){
  int c, i = 0;

  for( c = '0'; c <= '9'; c++ ){
    val[c] = i;
    i++;
  }

  for( c = 'A'; c <= 'Z'; c++ ){
    val[c] = i;
    i++;
  }

  for( c = 'a'; c <= 'z'; c++ ){
    val[c] = i;
    i++;
  }
}

int main(){
  FILE *fin, *fout;
  int c, la, lb, max, nans, ha, hb, i;

  init();

  fin = fopen( "strmatch.in", "r" );

  la = 0;
  while( isalpha( c = fgetc( fin ) ) || isdigit( c ) )
    a[la++] = val[c];

  lb = 0;
  while( isalpha( c = fgetc( fin ) ) || isdigit( c ) )
    b[lb++] = val[c];

  fclose( fin );

  max = 1;
  for( i = 0; i < la - 1; i++ )
    max = ((long long)max * BAZA ) % MOD;

  ha = hb = 0;
  for( i = 0; i < la; i++ ){
    ha = ((long long)ha * BAZA + a[i]) % MOD;
    hb = ((long long)hb * BAZA + b[i]) % MOD;
    //printf( "%d %d\n", a[i], b[i] );
  }

  nans = 0;
  if( ha == hb )
    ans[nans++] = 0;

  //printf( "%d %d\n", ha, hb );

  for( i = la; i < lb; i++ ){
    hb = ((((long long)hb - max * b[i - la] + MOD) % MOD) * BAZA + b[i]) % MOD;
    if( ha == hb )
      ans[nans++] = i - la + 1;
  }

  fout = fopen( "strmatch.out", "w" );

  fprintf( fout, "%d\n", nans );
  for( i = 0; i < nans; i++ )
    fprintf( fout, "%d ", ans[i] );
  fprintf( fout, "\n" );

  fclose( fout );

  return 0;
}