Cod sursa(job #2589045)

Utilizator ViAlexVisan Alexandru ViAlex Data 25 martie 2020 18:30:45
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 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'))%MOD;
	}
	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=1;
	int result=0;

	for(int i=0;i<word_length;i++){
		base=(base*3)%MOD;
	}


	long long current=0;
	char here,first=text[0];

	for(int i=0;i<text.length();i++){
		here=text[i];
		current=(current*3+(here-'a'))%MOD;

		if(i>=word_length-1){
			
			if(i>=word_length){
				current=(current-base*(first-'a'))%MOD;
				first=text[i-word_length+1];
			}

			if(contains(current))
				result++;


		}
	}
	out<<result<<endl;
}


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