Mai intai trebuie sa te autentifici.

Cod sursa(job #3369478)

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

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

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 );

  if( la <= lb ){
    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 );

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

  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;
}