Pagini recente » Cod sursa (job #420175) | Cod sursa (job #2406112) | Cod sursa (job #1294140) | Cod sursa (job #2001911) | Cod sursa (job #798079)
Cod sursa(job #798079)
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define MAXL 10000005
#define MOD 666013
#define MAXP 25
vector < long long int > v[ MOD ];
long long int t[ MAXL ];
long long int aux;
int n, m, i, p, b = 4, res;
char S[ MAXL ], P[ MAXP ];
inline int search_value(long long int val)
{
int l;
vector < long long int > :: iterator ii;
l = val % MOD;
for(ii = v[l].begin(); ii != v[l].end(); ++ii)
if(*ii == val)
return 1;
return 0;
}
inline void insert_value(long long int val)
{
int l;
vector < long long int > :: iterator ii;
l = val % MOD;
v[l].push_back(val);
}
long long int POW(int a, int b)
{
long long int res = 1;
while(b)
res = (long long) res * a, --b;
return res;
}
int main()
{
FILE *f = fopen("abc2.in", "r");
fgets(S, 10000002, f);
n = strlen(S) - 2;
fgets(P, 22, f);
m = strlen(P) - 2;
for(i = 0; i <= m; ++i)
aux = aux * b + (S[i] - 'a' + 1);
t[m] = aux;
for(i = m + 1; i <= n; ++i)
t[i] = (t[i-1] - (S[i-m-1] - 'a' + 1) * POW(b, m)) * POW(b, m-2) + S[i] - 'a' + 1;
while(!feof(f))
{
if(strlen(P) - 2 == m)
{
aux = 0;
for(i = 0; i <= m; ++i)
aux = aux * b + (P[i] - 'a' + 1);
if(!search_value(aux))
insert_value(aux);
}
fgets(P, 22, f);
}
fclose(f);
for(i = m; i <= n; ++i)
if(search_value(t[i]))
++res;
FILE *g = fopen("abc2.out", "w");
fprintf(g, "%d\n", res);
fclose(g);
return 0;
}