Pagini recente » Cod sursa (job #1167167) | Cod sursa (job #775929) | Cod sursa (job #2479835) | Cod sursa (job #2904483) | Cod sursa (job #1471474)
#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) if(G) for ( hash_line* it = (G) ; it; it = it->next)
using namespace std;
int N, NB, ans, P1 = 1, P2 = 1, P3 = 1, set = 0;
char A[MAXA], B[MAXB];
struct hash_line{
int val1, val2;
hash_line* next;
} *Hash[MOD];
inline bool find_val(int key, int val1, int val2){
int list = key % MOD;
foreach(Hash[list])
if (it->val1 == val1 && it->val2 == val2) return 1;
return 0;
}
inline void insert_val(int key, int val1, int val2){
int list = key % MOD;
foreach(Hash[list]) if (it->val1 == val1 && it->val2 == val2) return;
hash_line *New = new hash_line;
New->val1 = val1, New->val2 = val2, New->next = Hash[list];
Hash[list] = New;
}
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_val(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 += find_val(hash1, hash2, hash3);
}
printf("%d\n", ans);
return 0;
}