Pagini recente » Cod sursa (job #479936) | Cod sursa (job #1145196) | Cod sursa (job #646970) | Autentificare | Cod sursa (job #112824)
Cod sursa(job #112824)
#include <stdio.h>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;
#define in "abc2.in"
#define out "abc2.out"
#define dim 10000003
#define modulo 1000003
#define ull unsigned long long
int N=0,M;
int S[23];
char Cuvant[dim], linie[23];
// hashing sintax
typedef struct hash {
ull vf;
hash* next;
} *PHash;
PHash L[modulo], P;
void Add(ull,int);
bool Search(ull,int);
//
int main()
{
int NR, poz, Total=0;
ull X, H, H1;
bool ok;
FILE *fin = fopen(in,"r");
freopen(out,"w",stdout);
fgets(Cuvant,dim-1,fin);
while ( Cuvant[N] >= 'a' && Cuvant[N] <= 'c' ) N++;
while ( fgets(linie,22,fin) )
{
poz = 0;
while ( linie[poz] >= 'a' && linie[poz] <= 'c' ) poz++;
M = poz;
H = (int)(pow(3,poz-1)), X = 0, poz = 0;
while ( H )
{
X += ((int)linie[poz]-96)*H;
H /= 3, poz++;
}
ok = 0;
NR = X % modulo;
P = L[NR];
while ( P && !ok )
{
if ( P->vf == X ) ok = 1;
else P = P->next;
}
if ( ok ) continue; // il am deja in hash
Add(X,NR);
}
ull T;
H = H1 = (int)pow(3,M-1);
for ( int i = 0; i <= N-M; i++ )
{
T = 0, H = H1;
for ( int j = i; j < i+M; j++ )
{
T += ((int)(Cuvant[j]-96))*H;
H /= 3;
}
Total += Search(T, T % modulo);
}
printf("%d", Total);
}
bool Search(ull X, int NR)
{
bool ok = 0;
P = L[NR];
while ( P && !ok )
{
if ( P->vf == X ) ok = 1;
else P = P->next;
}
return ok;
}
void Add(ull X, int NR)
{
PHash P = new hash;
P->vf = X;
P->next = L[NR];
L[NR] = P;
}