Pagini recente » Cod sursa (job #1041293) | Cod sursa (job #3262184) | Cod sursa (job #1916451) | Cod sursa (job #2548409) | Cod sursa (job #1850718)
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#define MOD 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
struct
{
int nr = 0;
vector<unsigned int> str;
}v[666015];
string s,s1,s2;
char c;
long long dim, strln, putere, nr1, contor = 0;
void adaugareHash()
{
unsigned long long nr1 = 0,strln, putere = 1,e = 0;
for(int i = 0; i < s1.size(); ++i)
{ nr1+=putere*(s1[i]-'a');
putere *= 3;
}
if(v[nr1%MOD].nr == 0)
{
++v[nr1%MOD].nr;
v[nr1%MOD].str.push_back(nr1);
}
else
{ e = 0;
for(int i = 0; i < v[nr1%MOD].nr; ++i)
{
if(v[nr1%MOD].str[i] == nr1)
{
e = 1;
break;
}
}
if(e == 0)
{
++v[nr1%MOD].nr;
v[nr1%MOD].str.push_back(nr1);
//cout<<s1<<endl;
}
}
}
void citire()
{
unsigned int a = 0;
fin>>s;
strln = s.size();
while(fin>>s1)
{
adaugareHash();
}
dim = s1.size();
}
void verificare(unsigned int x)
{
unsigned int e = 0, k = dim - 1;
for(int i = 0; i < v[nr1%MOD].nr; ++i)
{
if (v[nr1%MOD].str[i]==nr1)
{
++contor;
break;
}
}
}
int main()
{ int i;
citire();
//cout<<dim<<endl;
nr1 = 0;
for(i = strln - 1; i >= strln - dim; --i)
{
nr1 *= 3;
if(s[i] == 'b')
{
nr1 += 1;
}
if(s[i] == 'c')
{
nr1 += 2;
}
}
if(v[nr1%MOD].nr > 0)
{
//cout<<"1";
verificare(strln-dim);
}
putere = powl(3, dim);
//cout<<putere<<endl;
for(int i = strln - dim - 1; i >= 0; --i)
{
nr1 *= 3;
nr1 -= putere * (s[i + dim]-'a');
nr1 += s[i]-'a';
if(v[nr1%MOD].nr > 0)
{
verificare(i);
}
}
fout<<contor;
return 0;
}