Pagini recente » Cod sursa (job #2947356) | Cod sursa (job #2781912) | Cod sursa (job #458390) | Cod sursa (job #899655) | Cod sursa (job #1751213)
#include <string.h>
#include <stdio.h>
#include <vector>
#define Nmax 10000001
#define Mmax 50001
#define MOD 666013
using namespace std;
vector <int> hashmap[MOD + 11];
long long h[21];
char text[Nmax],cuv[Mmax];
int exists (int hash_value)
{
int key = hash_value % MOD;
for(vector<int>:: iterator it = hashmap[key].begin(); it != hashmap[key].end(); it++)
if (*it == hash_value)
return 1;
return 0;
}
int main()
{
int sol = 0;
int hash_value = 0, n, m;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
h[0] = 1;
for(int i = 1; i <= 20; i++)
h[i] = 3 * h[i-1];
fgets(text, Nmax, stdin);
while (fgets(cuv,Mmax,stdin) != NULL)
{
hash_value = 0;
n = strlen(cuv) - 1;
cuv[n] = 0;
for( int i = 0; i < n; i++)
hash_value += ( cuv[i] - 'a' ) * h[i];
if ( !exists(hash_value))
hashmap[hash_value % MOD].push_back(hash_value);
}
hash_value = 0;
for (int i = 0; i < n; i++)
hash_value += (text[i] - 'a' ) * h[i];
if(exists(hash_value))
++sol;
m = strlen(text) - 1;
for(int i = n; i < m; i++)
{
hash_value /= 3;
hash_value += (text[i] - 'a' ) * h[n - 1];
if (exists(hash_value))
++sol;
}
printf("%d", sol);
return 0;
}