Cod sursa(job #2648395)

Utilizator euyoTukanul euyo Data 10 septembrie 2020 17:33:49
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int H = 3337333;
const int B = 3; 
const int MaxN = 10000002;
const int MaxC = 22;

char f[H + 1];
char txt[MaxN];
char word[MaxC];

int main() {
  int lt, lw, basep;
  
  fin >> txt;
  lt = strlen( txt );
  while ( fin >> word ) {
	lw = strlen( word );
    int hash = 0;
	basep = 1;
	for ( int i = 0; i < lw; ++i ) {
	  hash = ((word[i] - 'a') + hash * B) % H;
	  if ( i != 0 ) {
		basep = (basep * B) % H;
	  }
	}
	f[hash] = 1;
  }
  int hash = 0, res = 0;
  for ( int i = 0; i < lw; ++i ) {
	hash = ((txt[i] - 'a') + hash * B) % H;
  }
  res += f[hash];
  for ( int i = lw; i < lt; ++i ) {
	hash = (((hash + H - (basep * (txt[i - lw] - 'a')) % H) % H) * B + txt[i] - 'a') % H;
    res += f[hash];
  }
  fout << res;
  fin.close();
  fout.close();
  return 0;
}