Cod sursa(job #960750)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 11 iunie 2013 01:30:20
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb

#include <fstream>
using namespace std;

struct THashNode;
typedef THashNode *PHashNode;
struct THashNode
{
    long long Num;
    PHashNode Next;
};

PHashNode MakeHashNode(long long x,PHashNode Next)
{
    PHashNode r = new THashNode();
    r->Num = x;
    r->Next = Next;
    return r;
}

#define Hash_Prime 30031
//510511

PHashNode HashTable[Hash_Prime];

char Data[10000005];
long Len = 0;

long SearchDict(long long x)
{
    long long p = x % Hash_Prime;
    PHashNode HN = HashTable[p];
    while (HN != 0)
    {
        if (HN->Num == x)
        {
            return 1;
        }
        HN = HN->Next;
    }
    return 0;
}

void ReadStrings(fstream &fin)
{
    char D[25];
    while (fin >> D)
    {
        long long z = 0;
        long long p;
        long a;

        for (a = 0;D[a] != 0;a += 1)
        {
            z = (z * 3) + (D[a] - 'a');
        }
        Len = a;

        if (SearchDict(z) == 0)
        {
            p = z % Hash_Prime;
            HashTable[p] = MakeHashNode(z,HashTable[p]);
        }
    }
}

int main(void)
{
    fstream fin("abc2.in",ios::in);
    fstream fout("abc2.out",ios::out);

    fin >> Data;

    ReadStrings(fin);

    long Count = 0;

    long long Val = 0;
    long long Mod = 1;
    for (long a = 0;a < Len - 1;a += 1)
    {
        Val = (Val * 3) + (Data[a] - 'a');
        Mod *= 3;
    }    

    for (long a = Len - 1;Data[a] != 0;a += 1)
    {
        Val = ((Val % Mod) * 3) + (Data[a] - 'a');
        Count += SearchDict(Val);
    }

    fout << Count;

    fin.close();
    fout.close();
    return 0;
}