Cod sursa(job #2303812)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 16 decembrie 2018 22:14:56
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
//Deşteaptă-te, române, din somnul cel de moarte,
//În care te-adânciră barbarii de tirani!
//Acum ori niciodată croieşte-ţi altă soartă,
//La care să se-nchine şi cruzii tăi duşmani!
//https://Versuri.ro/w/v0l2
//
//Acum ori niciodată să dăm dovezi în lume
//Că-n aste mâni mai curge un sânge de roman,
//Şi că-n a noastre piepturi păstrăm cu fală-un nume
//Triumfător în lupte, un nume de Traian!

#include <bits/stdc++.h>
#define mod 9973
using namespace std;
char s[10000005],p[25];
int n,t,sol;
unsigned int t3=1,cod;
vector <unsigned int> v[mod];
bool caut(unsigned int x)
{
    int cod=x%mod;
    for(int i=0;i<v[cod].size();++i) if(v[cod][i]==x) return 1;
    return 0;
}
void baga(unsigned int x)
{
    int cod=x%mod;
    for(int i=0;i<v[cod].size();++i) if(v[cod][i]==x) return;
    v[cod].push_back(x);
}
int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    scanf("%s",s);
    n=strlen(s);
    while(scanf("%s",p)!=EOF)
    {
        t=strlen(p);
        cod=0;
        for(int i=0;i<t;++i) cod=cod*3+(p[i]-'a');
        baga(cod);
    }
    for(int i=1;i<t;++i) t3*=3;
    cod=0;
    for(int i=0;i<t;++i) cod=cod*3+(s[i]-'a');
    for(int i=0;i<n-t+1;++i)
    {
        sol+=caut(cod);
        cod=(cod-t3*(s[i]-'a'))*3+(s[i+t]-'a');
    }
    printf("%d\n",sol);
	return 0;
}