Cod sursa(job #2589054)

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

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

#define MOD 100000007

string text;
int word_length;

unordered_set<long long> words;


bool contains(long long word){
	return words.find(word)!=words.end();
}


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){
		words.insert(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;
}