Pagini recente » Cod sursa (job #2612981) | Cod sursa (job #1305137) | Cod sursa (job #2425205) | Cod sursa (job #721938) | Cod sursa (job #2296887)
#include <bits/stdc++.h>
#define M 10000010
#define MOD 10041
using namespace std;
unsigned long long CalcMask(char *s, int n)
{
unsigned long long p = 1;
unsigned long long sum = 0;
for(int i=n - 1; i>=0; i--) {
sum = (s[i] - 'a')*p+sum;
p *= 3;
}
return (sum);
}
void RenewMask(char *s, int n, int start, int pk, unsigned long long &x)
{
unsigned long long aux = (s[start+n] - 'a') + 3 * x - (s[start] - 'a')*pk;
x = aux;
}
vector<unsigned long long> h[MOD+5];
bool isIn(unsigned long long x){
int r = x%MOD;
for(int i = 0; i < h[r].size();++i){
if(h[r][i] == x)
return true;
}
return false;
}
int main ()
{
ifstream in("abc2.in");
ofstream out("abc2.out");
char sir[M], s[22];
in.getline(sir, M);
int n;
unsigned long long pk=1;
in.getline(s, 22);
n = strlen(s);
h[CalcMask(s, n)%MOD].push_back(CalcMask(s,n));
while(in.getline(s, 22)) {
unsigned long long tmp = CalcMask(s,n);
h[tmp%MOD].push_back(tmp);
}
for (int i=0;i<n;++i){
pk*=3;
}
unsigned long long x = CalcMask(sir, n);
int ct = 0;
if(isIn(x)) {
ct ++;
}
int m = strlen(sir);
for(int i=0; i<m-n; i++) {
RenewMask(sir, n, i, pk, x);
if(isIn(x)) {
ct ++;
}
}
out << ct;
return 0;
}