Pagini recente » Cod sursa (job #933720) | Cod sursa (job #1363315) | Cod sursa (job #2372201) | Cod sursa (job #2135649) | Cod sursa (job #2588941)
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
typedef long long LL;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int M = 666019, N = 50020;
LL l = 25;
LL val[N], urm[N], lst[M];
int nr;
string text;
string word;
LL cod3(string s)
{
LL c = 0;
for (unsigned int i = 0; i < s.length(); i++)
{
c = c * 3 + (s[i] - 'a');
}
return c;
}
bool apartine(LL 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(LL x)
{
int c = x % M;
if(apartine(x))
{
return;
}
val[++nr] = x;
urm[nr] = lst[c];
lst[c] = nr;
}
int main()
{
in >> text;
while(in >> word)
{
adauga(cod3(word));
}
in.close();
l = word.length();
LL r = 0, c = cod3(text.substr(0, l));
if (apartine(c))
{
r++;
}
//p3 = 3 la l - 1
LL p3 = 1;
int cop = l - 1;
while(cop--)
{
p3 *= 3;
}
for (unsigned int i = l; i < text.length(); i++)
{
c = c % p3 * 3 + (text[i] - 'a');
if (apartine(c))
{
r++;
}
}
out << r;
out.close();
return 0;
}