Cod sursa(job #2795760)

Utilizator vladburacBurac Vlad vladburac Data 6 noiembrie 2021 22:22:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <string.h>
using namespace std;
#define BASE 256
#define MOD1 666031
#define MOD2 1000007
const int MAXLEN = 2e6;

char pattern[MAXLEN+1], str[MAXLEN+1];
int poz[1001];
int main() {
  FILE *fin, *fout;
  int lenp, lenstr, hash1, hash2, Hash1, Hash2, nrap, put1, put2, i;
  fin = fopen( "strmatch.in", "r" );
  fgets( pattern, sizeof(pattern), fin );
  lenp = strlen(pattern);
  fgets( str, sizeof(str), fin );
  lenstr = strlen(str);
  lenp--;
  lenstr--;
  pattern[lenp] = str[lenstr] = 0;
  fclose( fin );

  hash1 = hash2 = 0;
  Hash1 = Hash2 = 0;
  put1 = put2 = 1;
  for ( i = 0; i < lenp; i++ ) {
    hash1 = ( hash1 * BASE + pattern[i] ) % MOD1;
    if( i < lenp - 1 )
      hash2 = ( hash2 * BASE + str[i] ) % MOD1;

    Hash1 = ( Hash1 * BASE + pattern[i] ) % MOD2;
    if( i < lenp - 1 )
      Hash2 = ( Hash2 * BASE + str[i] ) % MOD2;

    if( i < lenp - 1 ) {
      put1 = ( put1 * BASE ) % MOD1;
      put2 = ( put2 * BASE ) % MOD2;
    }
  }
  nrap = 0;
  for( i = lenp - 1; i < lenstr; i++ ) {
    hash2 = ( hash2 * BASE + str[i] ) % MOD1;
    Hash2 = ( Hash2 * BASE + str[i] ) % MOD2;
    if( hash1 == hash2 && Hash1 == Hash2 ) {
      nrap++;
      if( nrap <= 1000 )
        poz[nrap-1] = i + 1 - lenp;
    }
    hash2 = ( hash2 - put1 * str[i-lenp+1] ) % MOD1;
    Hash2 = ( Hash2 - put2 * str[i-lenp+1] ) % MOD2;
    if( hash2 < 0 )
      hash2 += MOD1;
    if( Hash2 < 0 )
      Hash2 += MOD2;
  }
  fout = fopen( "strmatch.out", "w" );
  fprintf( fout, "%d\n", nrap );
  i = 0;
  while( i < nrap ) {
    fprintf( fout, "%d ", poz[i] );
    i++;
  }
  fclose( fout );
  return 0;
}