Pagini recente » Cod sursa (job #966486) | Cod sursa (job #3183417) | Cod sursa (job #1130735) | preONI 2008 | Cod sursa (job #2296891)
#include <bits/stdc++.h>
#define M 10000010
#define MOD 10041
using namespace std;
inline 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);
}
inline void RenewMask(char *s, int n, int start, unsigned long long pk, unsigned long long &x)
{
unsigned long long aux = (x - (s[start] - 'a')*pk)*3 + s[start+n]- 'a' ;
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;
}
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;
}