Cod sursa(job #2588931)

Utilizator Ioan_AnghelIoan Anghel Ioan_Anghel Data 25 martie 2020 16:28:11
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <string>
#include <fstream>

using namespace std;

typedef long long LL;

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

const int M = 666019, N = 50020;
LL l = 25;
LL val[N], urm[N], lst[M];
int nr;

string text;
string word;

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

bool apartine(LL 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(int x)
{
    int c = x % M;
    if(apartine(x)){
        return;
    }
    val[++nr] = x;
    urm[nr] = lst[c];
    lst[c] = nr;
}

int main()
{
    in >> text;
    int L = text.length();
    while(in >> word){
        adauga(cod3(word));
    }
    l = word.length();
    LL r = 0, c = cod3(text.substr(0, l));
    if (apartine(c))
    {
        r++;
    }
    //p3 = 3 la l - 1
    int p3 = 1, cop = l - 1;
    while(cop--){
        p3 *= 3;
    }
    for (unsigned int i = l; i < text.length(); i++)
    {
        c = c % p3 * 3 + (text[i] - 'a');
        if (apartine(c))
        {
            r++;
        }
    }

    out << r;

    return 0;
}