Cod sursa(job #101727)

Utilizator andrei_infoMirestean Andrei andrei_info Data 13 noiembrie 2007 19:39:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.44 kb
#include <cstdio>
#include <string>

using namespace std;

typedef struct nod {
                int nr;
                nod *fiu[3];
                } nod;

nod rad; //radacina arborelui
char T[10000000], P[25];
int N,M,rez,MAX;

void adauga ( int poz, nod *pnod)
{
      if (poz == MAX)
      {
        pnod->nr++;
        return;
      };
      if (pnod->fiu[T[poz]-'a'] == NULL)
      {
                nod *aux;
                aux = new nod;
                aux->nr = 0;
                for (int i=0; i<=2; i++)   aux->fiu[i] = NULL;
                pnod->fiu[T[poz]-'a'] = aux;
      };
      adauga(poz+1, pnod->fiu[T[poz]-'a']);
};

int cauta( char *cuv, nod *pnod)
{
    if (cuv[0] == 0)
    {
        int aux = pnod->nr;
        pnod->nr = 0;
        return aux;
    };

    if (pnod->fiu[cuv[0]-'a'] == NULL)
        return 0;
    return cauta(cuv+1, pnod->fiu[cuv[0]-'a']);
};


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

        gets(T);
        gets(P);
        N = strlen(T);
        M = strlen(P);

        for (int i = 0; i<=N-M; i++)
        {
            MAX = i + M;
            adauga(i,&rad);
        };
        rez+=cauta(P,&rad);
        for ( gets(P); !feof(stdin); gets(P) )
        {
            rez+=cauta(P,&rad);
        };

        printf("%d", rez);
        fclose(stdout);
        fclose(stdin);
        return 0;
};