Cod sursa(job #2588937)

Utilizator rares9991Matisan Rares-Stefan rares9991 Data 25 martie 2020 16:31:56
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N=50001;
const int M=666019;

long long p3;

unsigned int lst[M], urm[N], val[N], nr, l;
string text;
string cuv;

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

void adauga(unsigned int x)
{
    int c = x % M;
    if(apartine(x))
        return;
    val[++nr]=x;
    urm[nr]=lst[c];
    lst[c]=nr;
}

long long pow(unsigned int x,unsigned int y)
{
    if(y == 0)
        return 1;
    if(y % 2 == 0)
        return pow(x * x, y / 2);
    return x * pow(x * x, y / 2);
}

unsigned int cod3(string t)
{
    unsigned int c=0;
    for(unsigned int i=0; i<t.length(); i++)
        c=c*3+ (t[i] - 'a');
    return c;
}

int main()
{
    in>>text;
    while(in>>cuv)
    {
        adauga(cod3(cuv));
    }
    l=cuv.length();
    unsigned int r=0;
    unsigned int c=cod3(text.substr(0, l));
    if(apartine(c))
        r++;
    p3=pow(3, l-1);
    for(unsigned int i=l; i < text.length(); i++)
    {
        c=c % p3 * 3 + (text[i] - 'a');
        if (apartine(c))
            r++;
    }
    out<<r;
    return 0;
}