Cod sursa(job #2581521)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 15 martie 2020 13:53:44
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <fstream>
using namespace std;

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

const int L = 10000000;
const int l = 20;
const long long K = 666019;
const int dic = 50000;

char text[L];
char cuv[l];

int idx;
long long val[dic];
int urm[dic], lst[K];

bool apartine(long long x){
	int c = x % K;
	for(int p=lst[c]; p!=0; p=urm[p])
		if(val[p] == x)
			return true;
	return false;
}

void adauga(long long x){
	if(apartine(x))
		return;
	int c = x % K;
	val[++idx] = x;
	urm[idx] = lst[c];
	lst[c] = idx;
}

int characterValue(char c){
	return c - 'a';
}

int main()
{
	int ans,i,lengthT, length;
	long long nr,p;
	fin >> text;
	lengthT = (int)strlen(text);
	while(fin >> cuv){
		nr = 0;
		length = (int)strlen(cuv);
		for(i=0; i<length; i++)
			nr = nr * 3 + 1LL * characterValue(cuv[i]);
		adauga(nr);
	}
	if(lengthT < length){
		fout << "0\n";
		return 0;
	}
	nr = 0, ans = 0;
	p = 1;
	for(i=0; i<length; i++){
		nr = nr * 3 + 1LL * characterValue(text[i]);
		p *= 3;
	}
	if(apartine(nr))
		ans++;
	p /= 3;
	for(; i<lengthT; i++){
		nr = (nr - p * characterValue(text[i-length])) * 3 + 1LL * characterValue(text[i]);
		if(apartine(nr))
			ans++;
	}
	fout << ans << "\n";
	return 0;
}