Cod sursa(job #2587487)

Utilizator matei123Biciusca Matei matei123 Data 22 martie 2020 18:57:47
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("abc2.in");
ofstream out ("abc2.out");
const int L = 10000001;
const int l = 21;
const long long K = 666019;
const int dic = 50001;
char text[L],cuv[l];
long long val[dic];
int urm[dic],lst[K],idx;
bool apartine (int 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 (int x)
{   if (apartine(x)) return;
    int c=x%K;
    val[++idx]=x;
    urm[idx]=lst[c];
    lst[c]=idx;
}
int main()
{   int ans,i,lengthT, length;
	long long nr,p;
	in >> text;
	lengthT = (int)strlen(text);
	while(in >> cuv)
    {   nr = 0;
		length = (int)strlen(cuv);
		for(i=0; i<length; i++)
			nr = nr * 3 + 1LL *(cuv[i]-'a');
		adauga(nr);
	}
	if(lengthT < length)
	{   out << "0\n";
		return 0;
	}
	nr = 0, ans = 0;
	p = 1;
	for(i=0; i<length; i++)
	{   nr = nr * 3 + 1LL * (text[i]-'a');
		p *= 3;
	}
	if(apartine(nr)) ans++;
	p /= 3;
	for(; i<lengthT; i++)
    {   nr = (nr - p * (text[i-length]-'a')) * 3 + 1LL * (text[i]-'a');
		if(apartine(nr)) ans++;
	}
	out << ans << "\n";
    return 0;
}