Cod sursa(job #2227092)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 31 iulie 2018 11:36:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <cstring>
#define maxn 2000000
#define pow1 73
#define mod1 100007
#define mod2 100019

using namespace std;

char a[maxn+5];
char v[maxn+5];

int match[maxn+5];
int ind = 0;

int main ()
{
  ifstream fin ( "strmatch.in" );
  ofstream fout ( "strmatch.out" );

  fin >> a >> v;

  int hashc1 = 0, hashc2 = 0; /// hash corect
  int hasht1 = 0, hasht2 = 0; /// hash test
  int i, la = strlen ( a ), lv = strlen ( v );

  if ( la > lv )
  {
    fout << '0';
    return 0;
  }

  int p1 = 1, p2 = 1;

  for ( i = 0; i < la - 1; i++ )
  {
    p1 = ( p1 * pow1 ) % mod1;
    p2 = ( p2 * pow1 ) % mod2;
  }

  /// hash corect
  for ( i = 0; i < la; i++ )
  {
    hashc1 = ( hashc1 * pow1 + a[i] ) % mod1;
    hashc2 = ( hashc2 * pow1 + a[i] ) % mod2;
  }

  /// hash de start
  for ( i = 0; i < la; i++ )
  {
    hasht1 = ( hasht1 * pow1 + v[i] ) % mod1;
    hasht2 = ( hasht2 * pow1 + v[i] ) % mod2;
  }

  for ( i = la; i < lv; i++ )
  {
    if ( hashc1 == hasht1 && hashc2 == hasht2 )
      match[ind++] = i - la;

    hasht1 = ( hasht1 - ( v[i-la] * p1 ) % mod1 + mod1 ) * pow1 + v[i];
    hasht1 %= mod1;

    hasht2 = ( hasht2 - ( v[i-la] * p2 ) % mod2 + mod2 ) * pow1 + v[i];
    hasht2 %= mod2;
  }

  if ( hashc1 == hasht1 && hashc2 == hasht2 )
    match[ind++] = i - la;

  fout << ind << '\n';

  if ( ind > 1000 )
    ind = 1000;

  for ( i = 0; i < ind; i++ )
    fout << match[i] << ' ';

  fin.close ();
  fout.close ();

  return 0;
}