Cod sursa(job #2588953)

Utilizator Ioan_AnghelIoan Anghel Ioan_Anghel Data 25 martie 2020 16:44:05
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 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;
unsigned int l = 25;
unsigned int val[N], urm[N], lst[M];
int nr;

string text;
string word;

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

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;
}

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

    out << r;

    out.close();
    return 0;
}