Pagini recente » Cod sursa (job #2895052) | Cod sursa (job #2274461) | Cod sursa (job #1226385) | Cod sursa (job #1875877) | Cod sursa (job #1727350)
#include <algorithm>
#include <fstream>
#include <cstring>
#include <set>
#include <map>
#define MOD 1000000007
using namespace std;
char cuv[50] , prop[10000005];
int n , m , nr;
int v[50005];
bool caut_bin(int val) {
int i , p = 0;
for (i = 1; i <= nr; i <<= 1);
while (i) {
if (i + p <= nr && v[i + p] <= val) {
p += i;
}
i >>= 1;
}
if (v[p] == val) {
return 1;
}
return 0;
}
int main() {
freopen("abc2.in" , "r" , stdin);
freopen("abc2.out" , "w" , stdout);
scanf("%s" , &prop);
m = strlen(prop);
while (scanf("%s" , &cuv) != EOF) {
int hash1 = 0;
n = strlen(cuv);
for (int i = 0; i < n; ++i) {
hash1 = (hash1 * 3 + (cuv[i] - 'a')) % MOD;
}
v[++nr] = hash1;
}
sort(v + 1, v + nr + 1);
int P1 = 1, hash1 = 0;
for (int i = 0; i < n; ++i) {
hash1 = (hash1 * 2 + (prop[i] - 'a')) % MOD;
if (i) {
P1 = (3 * P1) % MOD;
}
}
if (caut_bin(hash1) == 1) {
++sol;
}
for (int i = n; i < m; ++i) {
hash1 = ((hash1 - ((prop[i - n] - 'a') * P1) % MOD + MOD) * 3 + (prop[i] - 'a')) % MOD;
if (caut_bin(hash1) == 1) {
++sol;
}
}
printf("%d" , sol);
return 0;
}