Pagini recente » Cod sursa (job #2602436) | Cod sursa (job #817433) | Cod sursa (job #154788) | Cod sursa (job #1247159) | Cod sursa (job #1083169)
#include <fstream>
#include <cstring>
#include <vector>
#define getNumber(x) (x - 'a')
#define unsigned long long
using namespace std;
ifstream fin ("abc2.in");
ofstream fout ("abc2.out");
const unsigned NMAX = 10000009;
const unsigned M = 40009;
int N; char S[NMAX]; char P[30];
class Hash {
public:
vector<unsigned> H[M + 1];
void insert(unsigned value) {
H[value % M].push_back(value);
}
bool search(unsigned value) {
int ind = value % M;
for(unsigned i = 0 ;i < H[ind].size(); ++i)
if(value == H[ind][i])
return true;
return false;
}
};
Hash T;
void Read() {
fin >> S + 1;
while(!fin.eof()) {
fin >> P; unsigned h = 0;
N = strlen(P);
for(int i = 0 ; i < strlen(P) ; ++i)
h = h * 3 + getNumber(P[i]);
T.insert(h);
}
}
int main() {
Read ();
unsigned h = 0; unsigned cnt = 0; unsigned pw[22];
pw[0] = 1; for(int i = 1; i <= 21; ++i) pw[i] = pw[i - 1] * 3;
for(int i = 1; i <= N; ++i) h = h * 3 + getNumber(S[i]);
if(T.search(h)) cnt++;
for(int i = N + 1; i < strlen(S + 1) ; ++i) {
h -= getNumber(S[i - N]) * pw[N - 1];
h = h * 3 + getNumber(S[i]);
if(T.search(h)) cnt++;
}
fout << cnt <<'\n';
return 0;
}