Pagini recente » Cod sursa (job #54458) | Cod sursa (job #2732422) | Cod sursa (job #2077627) | Cod sursa (job #871608) | Cod sursa (job #1429240)
/*
Worg
*/
#include <cstdio>
#include <vector>
#include <cstring>
#define MOD 1000003
#define MOD_2 666013
#define DIM 10000010
#define sigma 5
using namespace std;
FILE *fin = freopen("abc2.in","r",stdin);
FILE *fout = freopen("abc2.out","w",stdout);
vector <int> Hash[ MOD ];
char T[ DIM ], F[ 30 ];
int len_1, len_2, rest_1, rest_2, x1, x2;
int val[300];
inline void giveValues()
{
x1 = 0, x2 = 0;
for(int i = 0; i < len_2; ++i)
{
x1 = (x1 * sigma + val[ F[i] ]) % MOD;
x2 = (x2 * sigma + val[ F[i] ]) % MOD_2;
}
}
inline bool Find(int q1, int q2)
{
for(int i = 0; i < Hash[q1].size(); ++i)
if( Hash[q1][i] == q2 )
return 1;
return 0;
}
void Read()
{
gets( T );
len_1 = strlen( T );
while( gets(F) )
{
len_2 = strlen( F );
giveValues();
Hash[x1].push_back(x2);
}
}
void Solve()
{
int i, q1 = 0, q2 = 0, ans = 0;
rest_1 = rest_2 = sigma;
for(i = 0; i < len_2; ++i)
{
q1 = (q1 * sigma + val[ T[i] ] ) % MOD;
q2 = (q2 * sigma + val[ T[i] ] ) % MOD_2;
if( i )
rest_1 = (rest_1 * sigma) % MOD,
rest_2 = (rest_2 * sigma) % MOD_2;
}
ans += Find(q1, q2);
for(i = len_2; i < len_1; ++i)
{
q1 = (q1 * sigma + val[ T[i] ] ) % MOD;
q2 = (q2 * sigma + val[ T[i] ] ) % MOD_2;
q1 -= val[ T[i - len_2] ] * rest_1;
q2 -= val[ T[i - len_2] ] * rest_2;
while(q1 < 0)
q1 += MOD;
while(q2 < 0)
q2 += MOD_2;
ans += Find(q1, q2);
}
printf("%d", ans);
}
int main()
{
val['a'] = 0, val['b'] = 1, val['c'] = 2;
Read();
if( len_2 > len_1 )
{
printf("0");
return 0;
}
Solve();
return 0;
}