Cod sursa(job #1886454)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 20 februarie 2017 21:39:44
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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 unsigned int 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()
{
    long long fact = 1;
    long long nr = 0;
    for (int i = strlen(text)-1, t = 0; i >= 0; i--, t++) {
        if (t <= n) {
            nr += fact*(text[i]-'a'+1);
            fact *= ((t<n)<<1) | 1;
        }
        else {
            nr -= (text[i+n+1]-'a'+1);
            nr /= 3;
            nr += fact*(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();
        fgets(cuv, MAXN+1, stdin);
    }
    solve();

    return 0;
}