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