Pagini recente » Cod sursa (job #213702) | Cod sursa (job #1498829) | Cod sursa (job #784190) | calcul | Cod sursa (job #101324)
Cod sursa(job #101324)
#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;
}