Pagini recente » Cod sursa (job #1821941) | Cod sursa (job #2418440) | Cod sursa (job #1650652) | Cod sursa (job #773099) | Cod sursa (job #2297703)
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD1 = 1000000007;
const int MOD2 = 1000000009;
const int LMAX = 10000005;
const int NMAX = 50005;
char s[LMAX];
char a[NMAX][25];
map <long long, long long> mp1;
map <long long, long long> mp2;
int p31[25];
int p32[25];
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
scanf("%s", s);
int m = (int)strlen(s);
int top = 1;
for( ; scanf("%s", a[top]) != EOF; top++);
top--;
int n = (int)strlen(a[1]);
for(int i = 1; i <= top; i++) {
long long nr1 = 0, nr2 = 0;
for(int j = 0; j < n; j++) {
nr1 = (nr1 * 3 + (a[i][j] - 'a')) % MOD1;
nr2 = (nr2 * 3 + (a[i][j] - 'a')) % MOD2;
}
mp1[nr1]++;
mp2[nr2]++;
}
long long nr3 = 1;
for(int i = 0; i <= 21; i++) {
p31[i] = nr3 % MOD1;
p32[i] = nr3 % MOD2;
nr3 *= 3;
}
if(m < n) {
printf("0\n");
return 0;
}
long long nr1 = 0, nr2 = 0;
for(int i = 0; i < n; i++) {
nr1 = (nr1 * 3 + (s[i] - 'a')) % MOD1;
nr2 = (nr2 * 3 + (s[i] - 'a')) % MOD2;
}
long long sol = 0;
if(mp1.find(nr1) != mp1.end() && mp2.find(nr2) != mp2.end()) {
sol++;
}
for(int i = n; i < m; i++) {
nr1 = (nr1 - (s[i - n] - 'a') * p31[n - 1] + MOD1) % MOD1;
nr2 = (nr2 - (s[i - n] - 'a') * p32[n - 1] + MOD2) % MOD2;
nr1 = (nr1 * 3 + (s[i] - 'a')) % MOD1;
nr2 = (nr2 * 3 + (s[i] - 'a')) % MOD2;
if(mp1.find(nr1) != mp1.end() && mp2.find(nr2) != mp2.end()) {
sol++;
}
}
printf("%lld\n", sol);
return 0;
}