Pagini recente » Cod sursa (job #219671) | Cod sursa (job #430376) | Cod sursa (job #2989996) | Cod sursa (job #2641789) | Cod sursa (job #219679)
Cod sursa(job #219679)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
#define MOD 666013
char s[10000505], cuv[205];
int rez, p[205], n, k, nr;
vector<int> hash[MOD + 1000];
int find(int x)
{
int poz = x % MOD, l = hash[poz].size();
for (int i = 0; i < l; i++) if (hash[poz][i] == x) return 1;
return 0;
}
int cmp(const void *i, const void *j)
{
return *(int*)i - *(int*)j;
}
void putere()
{
int i;
p[0] = 1;
for (i = 1; i <= 25; i++) p[i] = p[i - 1] * 3;
}
int transform(char s[], int n)
{
int x = 0, i;
for (i = 0; i < n; i++) x += (s[i] - 'a') * p[n - i - 1];
return x;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
int i, x;
putere();
fgets(s,10000501,stdin);
fgets(cuv,25,stdin);
k = strlen(cuv) - 1;
n = strlen(s) - 1;
x = transform(cuv, k);
hash[x % MOD].push_back(x);
while (!feof(stdin))
{
fgets(cuv,25,stdin);
x = transform(cuv,k);
hash[x % MOD].push_back(x);
}
x = 0;
for (i = 0; i < k; i++) x += (s[i] - 'a') * p[k - i - 1];
if (find(x)) rez++;
for (; i < n; i++)
{
x -= ((s[i - k] - 'a') * p[k - 1]);
x *= 3;
x += (s[i] - 'a');
if (find(x)) rez++;
}
printf("%d\n",rez);
return 0;
}