Pagini recente » Cod sursa (job #1647876) | Cod sursa (job #442867) | Cod sursa (job #2046455) | Cod sursa (job #1324712) | Cod sursa (job #1471471)
#define _CRT_SECURE_NO_DEPRECATE
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXA 10000005
#define MAXB 50005
#define P 73
#define MOD 25000
#define MOD1 100003
#define MOD2 1000021
#define MOD3 1000051
#define foreach(G) for(decltype((G).begin()) it = (G).begin(); it != (G).end(); ++it)
using namespace std;
int N, NB, ans, P1 = 1, P2 = 1, P3 = 1, set = 0;
char A[MAXA], B[MAXB];
vector <pair<int, int>> Hash[MOD];
inline void insert_hash(int key, int val1, int val2){
foreach(Hash[key % MOD])
if (it->first == val1 && it->second == val2) return;
Hash[key % MOD].push_back(make_pair(val1, val2));
}
inline int search_hash(int key, int val1, int val2){
foreach(Hash[key % MOD])
if (it->first == val1 && it->second == val2) return 1;
return 0;
}
int main(){
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
int hash1, hash2, hash3, len = 0;
gets(A);
N = strlen(A);
while (fgets(B, MAXB, stdin)){
if (!len) len = strlen(B) - 1;
hash1 = hash2 = hash3 = 0;
if (!NB) NB = len;
for (int i = 0; i < len; ++i){
hash1 = (hash1 * P + B[i]) % MOD1;
hash2 = (hash2 * P + B[i]) % MOD2;
hash3 = (hash3 * P + B[i]) % MOD3;
if (i && !set) P1 = (P1 * P) % MOD1, P2 = (P2 * P) % MOD2, P3 = (P3 * P) % MOD3;
}
set = 1;
insert_hash(hash1, hash2, hash3);
}
hash1 = hash2 = hash3 = 0;
for (int i = 0; i < N; ++i){
if (i >= NB)
hash1 = hash1 - (A[i - NB] * P1) % MOD1 + MOD1,
hash2 = hash2 - (A[i - NB] * P2) % MOD2 + MOD2,
hash3 = hash3 - (A[i - NB] * P3) % MOD3 + MOD3;
hash1 = (hash1 * P + A[i]) % MOD1;
hash2 = (hash2 * P + A[i]) % MOD2;
hash3 = (hash3 * P + A[i]) % MOD3;
if (i >= NB - 1) ans += search_hash(hash1, hash2, hash3);
}
printf("%d\n", ans);
return 0;
}