Cod sursa(job #2589058)

Utilizator ViAlexVisan Alexandru ViAlex Data 25 martie 2020 18:49:42
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<bits/stdc++.h>
using namespace std;

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


string text;
int word_length;


#define MOD1 666019
#define MOD2 746773


bool e1[MOD1];
bool e2[MOD2];




void add(long long to_add){
	e1[to_add%MOD1]=true;
	e2[to_add%MOD2]=true;
}



bool contains(long long word){
	
	return e1[word%MOD1] && e2[word%MOD2];
}


long long get_hash(const string&word){
	long long result=0;

	for(char a:word){
		
		result=(result*3+(a-'a'));
	}
	return result;
}

void read(){
	in>>text;
	string word;

	while(in>>word){
		add(get_hash(word));
	}

	word_length=word.length();
}


void solve(){
	long long base=pow(3,word_length-1);
	int result=0;

	long long current=get_hash(text.substr(0,word_length));
	if(contains(current))
		result++;

	for(int i=word_length;i<text.length();i++){
		
		current=(current-base*(text[i-word_length]-'a'))*3+(text[i]-'a');
		if(contains(current))
				result++;
	}
	out<<result;

}


int main(){
	read();
	solve();
	return 0;
}