Cod sursa(job #1248825)

Utilizator szabibibiOrban Szabolcs szabibibi Data 26 octombrie 2014 01:56:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <cstdio>

using namespace std;

#define PRIME_MAX 141650939
#define LMAX 10000000

char secv[LMAX + 3];
unordered_map<unsigned int, bool> map;
unsigned int pow3[20];

int cuv_len = 0;
int rez = 0;

unsigned int Convert(char *dict)
{
    unsigned int res = 0;
    for (int i = 0; i < cuv_len; i++)
    {
        res = res * 3 + dict[i] - 'a';
    }
    return res;
}

void Read()
{
    pow3[0] = 1;
    for (int i = 1; i < 20; i++)
        pow3[i] = pow3[i-1] * 3;

    FILE *f = fopen("abc2.in", "r");
    fgets(secv, LMAX + 3, f);

    char dict[23];
    bool first = true;
    while (NULL != fgets(dict, 23, f))
    {
        if (dict[0] == '\n' || dict[0] == '\r')
            continue;
        if (first)
        {
            cuv_len = strlen(dict);
            if (dict[cuv_len - 1] == '\n')
                cuv_len--;
            if (dict[cuv_len - 1] == '\r')
                cuv_len--;
            first = false;
        }
        map[Convert(dict)] = true;
    }

    fclose(f);
}

void Solve()
{
    unsigned int rhash = 0;
    for (int i = 0; i < cuv_len; i++)
    {
        if (secv[i] == 0)
            return;
        rhash = rhash * 3 + secv[i] - 'a';
    }

    int start = 0;
    int end = cuv_len - 1;
    while (secv[end] != 0 && secv[end] != '\r' && secv[end] != '\n')
    {
        if (map.find(rhash) != map.end())
        {
            rez++;
        }
        
        if (secv[end + 1] == 0 || secv[end + 1] == '\r' || secv[end + 1] == '\n')
            return;

        rhash = (rhash - pow3[cuv_len - 1] * (secv[start] - 'a')) * 3 + secv[end + 1] - 'a';
        start++;
        end++;
    }
}

void Write()
{
    FILE *f = fopen("abc2.out", "w");
    fprintf(f, "%d\n", rez);
    fclose(f);
}

int main()
{
    Read();
    Solve();
    Write();

    return 0;
}