Pagini recente » Cod sursa (job #371245) | Cod sursa (job #1008009) | Cod sursa (job #1990231) | Monitorul de evaluare | Cod sursa (job #2588940)
#include <bits/stdc++.h>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int N=50001;
const int M=666019;
unsigned int p3;
unsigned int lst[M], urm[N], val[N], nr, l;
string text;
string cuv;
bool apartine(unsigned int x)
{
int c=x%M;
for(int p=lst[c]; p!=0; p=urm[p])
{
if(val[p]==x)
{
return true;
}
}
return false;
}
void adauga(unsigned int x)
{
int c = x % M;
if(apartine(x))
return;
val[++nr]=x;
urm[nr]=lst[c];
lst[c]=nr;
}
unsigned int pow(unsigned int x,unsigned int y)
{
if(y == 0)
return 1;
if(y % 2 == 0)
return pow(x * x, y / 2);
return x * pow(x * x, y / 2);
}
unsigned int cod3(string t)
{
unsigned int c=0;
for(unsigned int i=0; i<t.length(); i++)
c=c*3+ (t[i] - 'a');
return c;
}
int main()
{
in>>text;
while(in>>cuv)
{
adauga(cod3(cuv));
}
l=cuv.length();
unsigned int r=0;
unsigned int c=cod3(text.substr(0, l));
if(apartine(c))
r++;
p3=pow(3, l-1);
for(unsigned int i=l; i < text.length(); i++)
{
c=c % p3 * 3 + (text[i] - 'a');
if (apartine(c))
r++;
}
out<<r;
return 0;
}