Pagini recente » Cod sursa (job #3220852) | Cod sursa (job #1131695) | Cod sursa (job #1711072) | Cod sursa (job #1327632) | Cod sursa (job #2295037)
#include<fstream>
#include<cstring>
#define M 393241
#define NMAX 10000075
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
struct node
{
long long info;
node *urm;
};
node *hashtable[M];
long long hfunction(long long x)
{
return x%M;
}
int searchnode(int value)
{
node *head = hashtable[hfunction(value)];
while (head != NULL && head->info != value)
{
head = head->urm;
}
if (head != NULL)
{
return 1;
}
return 0;
}
void addnode(int value)
{
node *first = new node;
first->info = value;
first->urm = hashtable[hfunction(value)];
hashtable[hfunction(value)] = first;
}
long long lcuvant,lsir,i;
int main()
{
char sir[NMAX],cuvant[30];
fin >> sir;
fin >> cuvant;
lcuvant = strlen(cuvant);
long long value=0;
for (i = 0; i <= lcuvant - 1; i++)
{
value = 3 * value + (cuvant[i] - 'a');
}
addnode(value);
while (fin >> cuvant)
{
long long value = 0;
for (i = 0; i <= lcuvant - 1; i++)
{
value = 3 * value + (cuvant[i] - 'a');
}
if (searchnode(value) == 0)
{
addnode(value);
}
}
long long p = 1;
for (i = 1; i <= lcuvant - 1; i++)
{
p = p * 3;
}
long long rh = 0;
for (i = 0; i <= lcuvant - 1; i++)
{
rh = 3 * rh + sir[i] - 'a';
}
long long sol=0;
sol = sol + searchnode(rh);
lsir = strlen(sir);
for (i = lcuvant; i <= lsir - 1; i++)
{
rh = rh - p * (sir[i - lcuvant] - 'a');
rh = 3 * rh + (sir[i] - 'a');
sol = sol + searchnode(rh);
}
fout << sol;
fin.close();
fout.close();
return 0;
}