Cod sursa(job #2202964)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 10 mai 2018 16:16:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <cstring>
#define maxn 2000000
#define pow1 73
#define mod1 100007
#define mod2 100019

using namespace std;

char a[maxn];
char v[maxn];

int match[maxn];
int ind = 0;

bool comp ( int st1, int dr1, int st2 )
{
  while ( st1 <= dr1 && a[st1] == v[st2] )
  {
    st1++;
    st2++;
  }
  return st1 > dr1;
}

char conv ( char ch )
{
  if ( ch >= 'a' && ch <= 'z' )
    return ch - 'a' + 1;
  else if ( ch >= 'A' && ch <= 'Z' )
    return 27 + ch - 'A';
  else
    return 53 + ch - '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 );

  for ( i = 0; i < la; i++ )
    a[i] = conv ( a[i] );

  for ( i = 0; i < lv; i++ )
    v[i] = conv ( v[i] );

  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 && comp ( 0, la - 1, i - la ) == true )
      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;
}