Pagini recente » Cod sursa (job #280057) | Cod sursa (job #3200533) | Cod sursa (job #2078298) | Cod sursa (job #1308469) | Cod sursa (job #2588840)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define K 666019
#define N 50005
#define M (LL)(1e7+5)
char s[M], cuv[25];
LL val[N], urm[N], lst[K], nr, vi, rez, p, cur;
int i, size_cuv;
void add(int x) {
val[++nr] = x;
urm[nr] = lst[x%K];
lst[x%K] = nr;
}
bool verify(LL x) {
for(int j = lst[x%K]; j; j = urm[j])
if(val[j] == x) return true;
return false;
}
LL pow_LL(LL x, LL y) {
if(y == 0) return 1;
if(y % 2ll == 0) return pow_LL(x * x, y / 2);
return x * pow_LL(x * x, y / 2);
}
int main() {
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> s;
while(fin >> cuv) {
for(i = cur = 0; cuv[i]; ++i)
cur = cur * 3ll + (LL)(cuv[i] - 'a');
add(cur); size_cuv = i;
}
p = pow_LL(3, size_cuv-1);
for(i = cur = 0; i < size_cuv; ++i)
cur = cur * 3ll + (LL)(s[i] - 'a');
rez += verify(cur);
for(; s[i]; ++i) {
cur = (cur - p * (LL)(s[i-size_cuv]-'a')) * 3ll + (LL)(s[i] - 'a');
rez += verify(cur);
}
fout << rez;
fin.close(); fout.close();
return 0;
}