Cod sursa(job #1886469)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 20 februarie 2017 21:48:17
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#define MAXT 10000050
#define MAXN 25

using namespace std;

char text[MAXT], cuv[MAXN];
int n, sol;
typedef long long ui;
unordered_map<long long, int> um;

inline void add()
{
    ui nr = 0;
    for (int i = 0; cuv[i]; i++)
        nr = nr*3 + (cuv[i]-'a'+1);
    um[nr]++;
}

void solve()
{
    ui fact = 1;
    ui nr = 0;
    for (int i = 0; i <= n; i++) {
        nr = nr*3 + (text[i]-'a'+1);
        fact *= 3;
    }
    fact /= 3;
    if (um.find(nr) != um.end())
        sol++;
    for (int i = n+1; text[i]; i++) {
        nr = (nr - (text[i-n-1]-'a'+1)*fact) * 3 + (text[i]-'a'+1);
        if (um.find(nr) != um.end())
            sol++;
    }
    printf("%d", sol);
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    gets(text);
    scanf("%s", cuv);
    n = strlen(cuv)-1;
    while (!feof(stdin)) {
        add();
        scanf("%s", cuv);
    }
    solve();

    return 0;
}