Pagini recente » Cod sursa (job #597495) | Cod sursa (job #1060313) | Cod sursa (job #2587019) | Cod sursa (job #1252713) | Cod sursa (job #2588970)
#include <fstream>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int N = 10000001, M = 666019;
string text, str, str1;
long long val[N];
int lst[N], urm[N], nr;
int caracter3(char c)
{
return c - 'a';
}
int hashf(string str)
{
long long c = 0;
for(int i = 0; i < str.length(); i++)
{
c = c * 3 + caracter3(str[i]);
}
return c;
}
int exista(long long x);
void adauga(string x)
{
long long cod = hashf(x);
int categ = cod % M;
if(exista(cod))
{
return;
}
val[++nr] = cod;
urm[nr] = lst[categ];
lst[categ] = nr;
}
int exista(long long x)
{
int categ = x % M;
for(int p = lst[categ]; p != 0; p = urm[p])
{
if(val[p] == x)
return 1;
}
return 0;
}
void sterge(int x)
{
int categ = x % M;
int p = lst[categ];
if(val[p] == x)
{
lst[categ] = urm[p];
return;
}
while(urm[p] != 0)
{
if(val[urm[p]] == x)
{
urm[p] = urm[urm[p]];
return;
}
p = urm[p];
}
}
int main()
{
long long lmax;
getline(in, text);
while(getline(in, str))
{
lmax = str.length();
adauga(str);
}
str1 = text.substr(0, lmax);
long long cod = hashf(str1), c = 0;
if(exista(cod))
c++;
long long p3 = pow(3, lmax - 1);
for(long long i = lmax; i < text.length(); i++)
{
cod = (cod - p3 * (text[i-lmax]-'a')) * 3 + (text[i]-'a');
if(exista(cod))
{
c++;
}
}
out << c;
return 0;
}