Cod sursa(job #2655418)

Utilizator euyoTukanul euyo Data 4 octombrie 2020 13:00:21
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin( "abc2.in" );
ofstream fout( "abc2.out" );

const int Mod = 777013;
const int B = 3; 
const int MaxN = 10000002;
const int MaxC = 22;

char txt[MaxN];
char word[MaxC];
vector<unsigned int> H[Mod];

int main() {
  int lt, lw, res = 0;
  unsigned int code, p;

  fin >> txt;
  lt = strlen( txt );
  while ( fin >> word ) {
	lw = strlen( word );
    code = 0;
	p = 1;
	for ( int i = 0; i < lw; ++i ) {
      code = code * B + word[i] - 'a'; 
	  p *= B;
	}
	H[code % Mod].push_back( code );
  }
  p /= B;
  code = 0;
  for ( int i = 0; i < lw; ++i ) {
    code = code * B + txt[i] - 'a';
  }
  int j = 0, k = code % Mod;
  while ( j < (int)H[k].size() && H[k][j] != code ) {
    ++j;
  }
  if ( j < (int)H[k].size() ) {
	++res;
  }
  for ( int i = lw; i < lt; ++i ) {
    code = (code - p * (txt[i - lw] - 'a')) * B + txt[i] - 'a';
	j = 0, k = code % Mod;
	while ( j < (int)H[k].size() && H[k][j] != code ) {
      ++j;
	}
	if ( j < (int)H[k].size() ) {
	  ++res;
	}
  }
  fout << res; 
  fin.close();
  fout.close();
  return 0;
}