Cod sursa(job #1368332)

Utilizator japjappedulapPotra Vlad japjappedulap Data 2 martie 2015 16:19:41
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream is ("abc2.in");
ofstream os ("abc2.out");

struct Node{
    int Nr;
    Node *son[3];
    Node()
    {
        Nr = 0;
        son[0] = son[1] = son[2] = 0;
    }
};

Node *Trie = new Node, *Hash = new Node;
char Main[10000001], C[22];
int N, Sol;

void Read();
inline void AddTrie(char *w, Node *X, int depth);
inline bool ExistsHash(char *w, Node *X);
inline void AddHash(char *w, Node *X);
inline int Count(char *w, Node *X);

int main()
{
    Read();
    for (; is >> C; )
        if (ExistsHash(C, Hash) == 0)
        {
            AddHash(C, Hash);
            Sol += Count(C, Trie);
        }
    os << Sol;
    is.close();
    os.close();
}

void Read()
{
    is >> Main;
    is >> C;
    N = strlen(C);
    int Msize = strlen(Main);
    for (int i = 0; i <= Msize-N; ++i)
        AddTrie(Main+i, Trie, 0);
    AddHash(C, Hash);
    Sol += Count(C, Trie);
};

inline int Count(char *w, Node *X)
{
    if (*w == 0)
        return X->Nr;
    if (X->son[*w - 'a'] == 0) return 0;
    return Count(w+1, X->son[*w - 'a']);
};

inline void AddHash(char *w, Node *X)
{
    if (*w == 0) return;
    if (X->son[*w - 'a'] == 0)
        X->son[*w - 'a'] = new Node;
    AddHash(w+1, X->son[*w - 'a']);
};

inline void AddTrie(char *w, Node *X, int depth)
{
    if (depth >= N || *w == 0)
    {
        X->Nr++;
        return;
    }
    if (X->son[*w - 'a'] == 0)
        X->son[*w - 'a'] = new Node;
    AddTrie(w+1, X->son[*w - 'a'], depth+1);
};

inline bool ExistsHash(char *w, Node *X)
{
    if (*w == 0)
        return 1;
    if (X->son[*w - 'a'] == 0)
        return 0;
    return ExistsHash(w+1, X->son[*w - 'a']);
};