Cod sursa(job #2257843)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 10 octombrie 2018 16:14:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#define maxl 2000000
#define pow1 73
#define mod 100007
#define maxaf 1000

using namespace std;

char a[maxl+5], v[maxl+5];
int match[maxaf+5];
int i_mt;

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

  fin >> a >> v;

  int la = strlen ( a ), lv = strlen ( v );
  int i, p = 1, hhc = 0, hht = 0;

  for ( i = 0; i < la; i++ )
  {
    if ( i < la - 1 )
      p = ( p * pow1 ) % mod;
    hhc = ( hhc * pow1 + a[i] ) % mod;
    hht = ( hht * pow1 + v[i] ) % mod;
  }

  for ( i = la; i < lv; i++ )
  {
    if ( hhc == hht )
    {
      if ( i_mt < maxaf )
        match[i_mt] = i - la;
      i_mt++;
    }
    hht = ( hht - ( v[i-la] * p ) % mod + mod ) * pow1 + v[i];
    hht %= mod;
  }

  if ( hhc == hht )
  {
    if ( i_mt < maxaf )
      match[i_mt] = i - la;
    i_mt++;
  }

  fout << i_mt << '\n';
  i_mt = min ( i_mt, maxaf );
  for ( i = 0; i < i_mt; i++ )
    fout << match[i] << ' ';

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

  return 0;
}