Pagini recente » Cod sursa (job #3216846) | Cod sursa (job #620870) | Cod sursa (job #241612) | Cod sursa (job #2141362) | Cod sursa (job #1838089)
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define FOREACH(it,a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define ld long double
#define ll long long
#define ull unsigned long long
const int base = 3;
const int modulo = 100663319;
const int MOD = 49157;
vector<int> H[MOD];
bool findHash(int x)
{
int g = x % MOD;
FOREACH(it,H[g])
if (*it == x) return 1;
return 0;
}
void addHash(int x)
{
int g = x % MOD;
H[g].push_back(x);
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string text,s;
fin >> text;
int len = 0;
while (fin >> s)
{
len = s.size();
int h = 0;
FOR(i,0,len-1)
{
h = h * base + (s[i] - 'a');
h = h % modulo;
}
if (!findHash(h)) addHash(h);
}
int h = 0;
int bpower = 1;
FOR(i,1,len-1)
bpower = bpower * base % modulo;
int sol = 0;
FOR(i,0,text.size()-1)
{
if (i < len) {
h = h * base + (text[i] - 'a');
h = h % modulo;
}
else {
h = h - bpower * (text[i - len] - 'a') % modulo + modulo;
h %= modulo;
h = h * base + (text[i] - 'a');
h = h % modulo;
}
if (i >= len-1)
{
if (findHash(h)) sol++;
}
}
fout << sol;
}