Pagini recente » Cod sursa (job #316451) | Cod sursa (job #1221162) | Cod sursa (job #3289806) | Cod sursa (job #3158683) | Cod sursa (job #2295904)
#include<fstream>
#include<cstring>
#include<math.h>
#define M 37215
#define N 10000045
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
struct node
{
unsigned int info;
node *urm;
};
node *hashtable[M];
char sir[N],cuv[25];
bool verify(unsigned int x)
{
node *first = hashtable[x%M];
while (first != NULL && first->info != x)
{
first = first->urm;
}
if (first != NULL)
{
return 1;
}
return 0;
}
void push(unsigned int x)
{
node *first = new node;
first->info = x;
first->urm = hashtable[x%M];
hashtable[x%M] = first;
}
unsigned int i;
int main()
{
fin >> sir;
fin >> cuv;
unsigned int lcuv = strlen(cuv);
unsigned int lsir = strlen(sir);
unsigned int x=0;
for (i = 0; i <= lcuv - 1; i++)
{
x = 3 * x + (cuv[i] - 'a');
}
push(x);
while (fin >> cuv)
{
x = 0;
for (i = 0; i <= lcuv - 1; i++)
{
x = 3 * x + (cuv[i] - 'a');
}
if (verify(x) == 0)
{
push(x);
}
}
unsigned int p =pow(3,lcuv-1);
unsigned int rollinghash = 0;
for (i = 0; i <= lcuv - 1; i++)
{
rollinghash = 3 * rollinghash + sir[i] - 'a';
}
long long ans=0;
ans = ans + verify(rollinghash);
for (i = lcuv; i <= lsir - 1; i++)
{
rollinghash = rollinghash - p * (sir[i - lcuv] - 'a');
rollinghash = 3 * rollinghash + (sir[i] - 'a');
ans = ans + verify(rollinghash);
}
fout << ans;
fin.close();
fout.close();
return 0;
}