Pagini recente » Cod sursa (job #1319130) | Cod sursa (job #2293550) | Cod sursa (job #899379) | Cod sursa (job #489778) | Cod sursa (job #1501041)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define maxN 10000002
#define maxW 50002
#define maxL 22
#define mod 6613
#define b 3
using namespace std;
int sol, n, j, l, nr, code, codes;
char s[maxN], a[maxW][maxL];
vector < int > V[mod];
int mycmp(int x, int y)
{
int i;
for (i = 0; i < l; ++ i)
if (a[x][i] != s[i + y])
return 0;
return 1;
}
int ok(int x, int p)
{
int i;
for (i = 0; i < V[x].size(); ++ i)
if (mycmp(V[x][i], p))
return 1;
return 0;
}
void read()
{
int nr = 0, i;
freopen("abc2.in", "r", stdin);
gets(s);
while (1)
{
a[++ nr][0] = 'd';
gets(a[nr]);
code = 0;
if (a[nr][0] == 'd')
{
-- nr;
return ;
}
if (nr == 1)
l = strlen(a[nr]);
for (i = 0; i < l; ++ i)
code = (code * b + a[nr][i] - 'a') % mod;
V[code].push_back(nr);
}
}
void solve()
{
int pbl = 1, i;
for (i = 1; i <= l; ++ i)
pbl = (pbl * b) % mod;
n = strlen(s);
for (i = 0; i < n; ++ i)
{
codes = (codes * b + s[i] - 'a') % mod;
if (i >= l - 1)
{
if (i - l >= 0)
codes = codes - (pbl * (s[i - l] - 'a')) % mod;
if (codes < 0)
codes += mod;
if (ok(codes, i - l + 1))
++ sol;
}
}
}
void write()
{
freopen("abc2.out", "w", stdout);
printf("%d\n", sol);
}
int main()
{
read();
solve();
write();
return 0;
}