Cod sursa(job #2443040)

Utilizator DavidLDavid Lauran DavidL Data 26 iulie 2019 12:07:00
Problema Abc2 Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int baza = 3;
 
int n, m;
char A[10000005];
char a[25];
ll v[50005];
int k;

signed main()
{
    FILE *fi, *fo;
    fi = fopen("abc2.in", "r");
    fo = fopen("abc2.out", "w");
 
    fgets(A + 1, 10000000, fi);
    n = strlen(A + 1);
    if (A[n] == '\n')
        n--;
 
    while (fgets(a + 1, 30, fi))
    {
        m = strlen(a + 1);
        if (a[m] == '\n')
            m--;
 
        long long cod = 0;
        for (int i = 1; i <= m; i++)
        {
            cod = 1LL * cod * baza + 1LL * (a[i] - 'a');
        }
        
        v[++k] = cod;
    }
 
    sort(v + 1, v + k + 1);
 
    if (n < m)
    {
        fprintf(fo, "0");
        return 0;
    }
 
    int rez = 0;
 
    long long p = 1;
    for (int i = 1; i < m; i++)
        p *= baza;
 
    long long cod = 0;
    for (int i = 1; i <= m; i++)
    {
        cod = cod * baza + (A[i] - 'a');
    }
 
    int poz = 1;
    for (int p = 15; p >= 0; p--)
        if (poz + (1 << p) <= k && v[poz + (1 << p)] <= cod)
            poz += (1 << p);
 
    if (v[poz] == cod)
        rez++;
 
    for (int i = m + 1; i <= n; i++)
    {
        cod -= p * (A[i - m] - 'a');
        cod = cod * baza + (A[i] - 'a');
 
        poz = 1;
        for (int p = 15; p >= 0; p--)
            if (poz + (1 << p) <= k && v[poz + (1 << p)] <= cod)
                poz += (1 << p);
    
        if (v[poz] == cod)
            rez++;
    }
 
    fprintf(fo, "%d", rez);
 
    return 0;
}