Cod sursa(job #2260495)

Utilizator tanasaradutanasaradu tanasaradu Data 15 octombrie 2018 08:32:46
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 fin ("abc2.in");
ofstream fout ("abc2.out");

const int Nmax =  10000005;
const int P = 123457;

char sir[Nmax + 5];

char a[50005][55];

int n , La , Lsir;

unordered_map < int , bool > M;


vector < int > L[P];

int main()
{
    int p = 1 , H = 0 , r , sol = 0;
    fin >> (sir + 1);
    Lsir = strlen(sir + 1);
    while(fin >> (a[++n] + 1))
        ;
    n--;
    La = strlen(a[1] + 1);
    if(La > Lsir)
    {
        fout << "0\n";
        return 0;
    }
    for(int i = 1 ; i <= La ; i++)
    {
        H = (H * 3 + (sir[i] - 'a')) % P;
        if(i > 1)
            p = (p * 3) % P;
    }
    r = H % P;
    L[r] . push_back(1);
    for(int i = La + 1 ; i <= Lsir ; i++)
    {
        H = (((H - (sir[i - La] - 'a') * p) % P + P) * 3 + (sir[i] - 'a')) % P;
        r = H % P;
        L[r] . push_back(i - La + 1);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        H = 0;
        for(int j = 1 ; j <= La ; j++)
            H = (H * 3 + (a[i][j] - 'a')) % P;
        r = H % P;
        for(auto it : L[r])
            if(!M[it])
            {
                sol++;
                M[it] = true;
            }
    }
    fout << sol << "\n";
    fin.close();
    fout.close();
    return 0;
}