Mai intai trebuie sa te autentifici.
Cod sursa(job #343299)
Utilizator | Data | 25 august 2009 14:23:10 | |
---|---|---|---|
Problema | Abc2 | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.06 kb |
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAX_N 10000005
#define MAX_M 1005
#define P 3
#define MOD 99987
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
char S[MAX_N];
int N, M, P1(1), H, Sol;
vector <int> G[MOD];
void insert(int x)
{
int k = x % MOD;
G[k].push_back(x);
}
int find(int x)
{
int k = x % MOD;
foreach(G[k])
if(*it == x)
return 1;
return 0;
}
void citire()
{
char s[MAX_M];
fgets(S, MAX_N, stdin);
N = strlen(S) - 1;
while(fgets(s, MAX_M, stdin))
{
int h = 0;
M = strlen(s) - 1;
for(int i = 0; i < M; ++i)
h = h * P + (s[i] - 'a');
insert(h);
//fprintf(stderr, "%d\n",h);
}
}
void solve()
{
for(int i = 0; i < M; ++i)
{
H = H * P + (S[i] - 'a');
if(i)
P1 *= P;
}
for(int i = M; i <= N; ++i)
{
//fprintf(stderr,"%d\n", H);
Sol += find(H);
H = (H - (S[i-M] - 'a')*P1) * P + (S[i] - 'a');
}
printf("%d\n",Sol);
}
int main()
{
freopen("abc2.in","rt",stdin);
freopen("abc2.out","wt",stdout);
citire();
solve();
}