Pagini recente » Cod sursa (job #812140) | Cod sursa (job #40863) | Cod sursa (job #352296) | Cod sursa (job #877988) | Cod sursa (job #955670)
Cod sursa(job #955670)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MAXN = 10000010, mod = 662013;
char v[MAXN], v1[25];
vector <unsigned int> has[mod];
int n, N, val[25], vect[MAXN], l;
long long sol;
unsigned int sum, put;
unsigned int putere(unsigned int p)
{
unsigned int i, nr=1;
for(i=0; i<p; ++i)
nr *= 3;
return nr;
}
unsigned int baza_10()
{
int i;
unsigned int nr_10 = 0, j;
j = put;
for(i=0; i<n; ++i, j/= 3)
nr_10 += val[i]*j;
return nr_10;
}
unsigned int baza10(long long i)
{
unsigned int nr_10=0, j;
long long k;
j = put;
for(k=i; k<i+n; ++k, j/= 3)
nr_10 += vect[k]*j;
return nr_10;
}
bool cautare(int aux, unsigned int val)
{
int i, j = has[aux].size();
bool ok=0;
for(i=0; i<j; ++i)
if(has[aux][i] == val)
{
ok = 1;
break;
}
return ok;
}
int main()
{
unsigned int aux=1, aux1, i;
fin.getline(v, MAXN);
N = strlen(v);
for(i=0; i<N; ++i)
{
if(v[i] == 'a')
vect[i] = 0;
else if(v[i] == 'b')
vect[i] = 1;
else
vect[i] = 2;
}
while(fin.getline(v1, 25))
{
if(n == 0){
n = strlen(v1);
put = putere(n-1);
}
for(i=0; i<n; ++i)
{
if(v1[i] == 'a')
val[i] = 0;
else if(v1[i] == 'b')
val[i] = 1;
else
val[i] = 2;
}
aux1 = baza_10();
aux = aux1%mod;
has[aux].push_back(aux1);
}
sum = baza10(0);
aux = sum%mod;
aux1 = cautare(aux, sum);
if(aux1 == 1)
++sol;
for(i=1; i+n<=N; ++i)
{
sum = (sum%put)*3 + vect[i+n-1];
aux = sum%mod;
aux1 = cautare(aux, sum);
if(aux1 == 1)
++sol;
}
fout << sol;
fin.close();
fout.close();
return 0;
}