Pagini recente » Cod sursa (job #1281208) | Cod sursa (job #1792313) | Cod sursa (job #2866633) | Cod sursa (job #2576413) | Cod sursa (job #2294550)
#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <fstream>
using namespace std;
const int p = 10003;
const int N = 100000001;
struct Nod
{
Nod *next;
int info;
} ;
int convert( char *s)
{
unsigned long long hh = 0 , pp = 1;
int i = strlen(s);
for ( ; i >= 0; i-- )
{
hh = hh * pp + (s[i]- '0');
pp *= 3;
}
return (int)(hh%p);
}
int h ( int x)
{
return x % p;
}
void inserare ( Nod ** v, int x )
{
Nod *prim ;
int poz = h(x);
for(prim = v[poz]; prim != NULL; prim = prim->next)
{
if ( prim ->info == x)
return;
}
Nod *aux = new Nod;
aux->next = NULL;
aux->info = x;
if( v[poz] == NULL )
v[poz] = aux;
else
{
aux->next = v[poz] ->next;
v[poz]->next = aux;
}
}
bool cautare( Nod** v, int x)
{
Nod * prim ;
if ( prim == NULL)
return false;
int poz = h(x);
for(prim = v[poz]; prim != NULL; prim = prim->next)
{
if ( prim ->info == x)
return true;
}
return false;
}
void dealloc ( Nod ** v)
{
int i;
for (i = 0; i < p; i++)
{
delete(v[i]);
}
delete(v);
}
int main()
{
ifstream in ("abc2.in");
ofstream out("abc2.out");
int nr, i, lcuv = 0, x, n;
char ch,mak[N];
Nod **v;
char cuv[21] ;
v = new Nod* [p+1];
for ( i = 0 ; i < p; i++)
{
v[i] = new Nod [p+1];
v[i] = NULL;
}
in >> mak >> cuv;
if(cuv[strlen(cuv)-1] == '\n')
cuv[strlen(cuv)-1] = '\0';
lcuv = strlen(cuv);
x = convert ( cuv );
inserare( v, x);
while (in >> cuv)
{
if(cuv[strlen(cuv)-1] == '\n')
cuv[strlen(cuv)-1] = '\0';
x = convert ( cuv );
inserare( v , x );
}
in.close();
nr = 0;
n = strlen(mak);
for ( i = lcuv; i < n; i++)
{
ch = mak[i];
mak[i] = 0;
x = convert(mak + i - lcuv );
if( cautare(v,x))
nr++;
mak[i] = ch;
}
out << nr;
out.close();
dealloc ( v );
return 0;
}