Cod sursa(job #2589063)

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

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


string text;
int word_length;


#define MOD 666013


vector<long long> hsh[MOD];

bool contains(long long value){
	int list=value%MOD;

	for(long long&a:hsh[list]){
		if(a==value)
			return true;
	}
	return false;
}


void add(long long to_add){
	int list=to_add%MOD;
	if(!contains(to_add))
		hsh[list].push_back(to_add);
}



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;
}