Pagini recente » Cod sursa (job #1233731) | Cod sursa (job #1006886) | Cod sursa (job #1470892) | Cod sursa (job #448041) | Cod sursa (job #106129)
Cod sursa(job #106129)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define nm 50010
#define lm 10000100
#define mod 666013
int n, sol;
char s[lm], a[nm][20];
vector<int> mat[666013];
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(s, 10000010, stdin);
while(!feof(stdin))
fgets(a[++n], 24, stdin);
--n;
for (int i = 1; i <= n; ++i) {
int crt = 0, m = strlen(a[i]) - 1;
for (int j = 0; j < m; ++j)
crt = (crt * 3 + a[i][j] - 'a') % mod;
mat[crt].push_back(i);
}
unsigned crt = 0;
int k = strlen(a[1]) - 1;
for (int i = 0; i < k - 1; ++i)
crt = crt * 3 + s[i] - 'a';
int sm = strlen(s) - 1, pow = 1;
for (int i = 1; i < k; ++i)
pow *= 3;
for (int i = k - 1; i < sm; ++i) {
crt = (unsigned)crt * 3 + s[i] - 'a';
int aux = (unsigned)crt % mod, m = mat[aux].size();
int ok = 0;
for (int j = 0; j < m; ++j) {
ok = 1;
for (int l = 0; l < k; ++l)
if (a[mat[aux][j]][l] != s[i - k + l + 1])
ok = 0;
}
sol += ok;
crt = crt - ((unsigned)s[i - k + 1] - 'a') * pow;
}
printf("%d\n", sol);
return 0;
}