Cod sursa(job #101324)

Utilizator mgntMarius B mgnt Data 13 noiembrie 2007 13:13:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int const MaxT = 10000000;
int const MaxD = 50000;
int const MaxC = 20;

static  int Prefix [2+MaxT];
static char Text   [2+MaxT];
static char Cuvant [2+MaxC];

class Copac {
public:
   Copac() { p[0] = 0; p [1] = 0; p[2] = 0;}
   ~Copac() {
    if (p [0]) delete p [0];
    if (p [1]) delete p [1];
    if (p [2]) delete p [2];
   }
  void Adauga(char * cuvant) {
    Copac ** x = p;
    Copac * y;
    while (4 != (*cuvant)) {
      y = x[(*cuvant)];
      if(0 == y) {
        y = new Copac;
        x[(*cuvant)] = y;
      }
      x = y->p;
      ++ cuvant;
    }
  }
public:
  Copac * p [3];
};

int const MaxPs = (3*3*3)*(3*3*3)*(3*3*3)*3;
int const MaxP  = 10;
Copac * pref [MaxPs];

int main () {
  int i, n, m, cont, j, pf, sm, m2, modpf;
  FILE * fin = fopen("abc2.in", "r");

  for(i=0;i<MaxPs;i++) pref[i]=0;

  fgets(Text, 2+MaxT, fin);
  n=-1+(int)strlen(Text);
  for(i=0;i<n;i++) Text[i]-='a';
  Text[n]='\0';

  Cuvant[0]='\0';
  fgets(Cuvant, 2+MaxC, fin);
  m=-1+(int)strlen(Cuvant);
  if(0<m) {
    if(MaxP<m) pf=MaxP; else pf=m;
    for(i=0;i<m;i++) Cuvant[i]-='a';
    Cuvant[m]=4;
    sm=0;for(i=0;i<pf;i++) sm=sm*3+Cuvant[i];
    if(0==pref[sm]) pref[sm]=new Copac;
    pref[sm]->Adauga(Cuvant);
  }
  
  while(true) {
    Cuvant[0]='\0';
    fgets(Cuvant, 2+MaxC, fin);
    if('\0' == Cuvant[0]) break;
    for(i=0;i<m;i++) Cuvant[i]-='a';
    Cuvant[m]=4;
    sm=0;for(i=0;i<pf;i++) sm=sm*3+Cuvant[i];
    if(0==pref[sm]) pref[sm]=new Copac;
    pref[sm]->Adauga(&Cuvant[pf]);
  }
  
  cont = 0;
  if(0 != m) {
    modpf=1;for(i=0;i<pf;i++) modpf *= 3;
    sm= 0; for(i=0;i<pf; i++) sm=3*sm+Text[i];
    Prefix[0]=sm;
    j=n-m;
    for(i=1;i<=j;i++) {
      sm=(3*sm+Text[i+pf-1])%modpf;
      Prefix[i]=sm;
    }
    m2=m-pf;

    Copac ** x;
    Copac * y;
    char * str;
    for(i = n-m; i >= 0; i --) {
      if(0==pref[Prefix[i]]) continue;
      Text[i+m] = 4;
      str=&Text[i];
      x=pref[Prefix[i]]->p;
      for(j=0;j<m2;j++) {
        y = x[str[j]];
        if(0 == y) break;
        x = y->p;
      }
      if(m2==j) ++ cont;
    }
  }
  FILE * fout = fopen("abc2.out", "w");
  fprintf(fout, "%d\n", cont);
  for(i=0;i<MaxPs;i++) if(0 != pref[i]) delete pref[i];
  fclose(fin);
  fclose(fout);
  return 0;
}