Pagini recente » Borderou de evaluare (job #2499319) | Borderou de evaluare (job #248727) | Borderou de evaluare (job #185783) | Borderou de evaluare (job #1542991) | Cod sursa (job #98618)
Cod sursa(job #98618)
#include<stdio.h>
const int lemax = 100000;
const int km = 10;
char a[lemax];
int i;
int prod[km];
int lung;
const int mod = 666013;
int an[km][mod + 2];
const int baz[9] = {0,3,33,13,17,23,71,73};
#include<string>
int hash[km];
int tab[mod * 30];
int k;
int ans;
char s[40];
int min(int i,int j)
{
return i > j ? j : i;
}
bool lit(char c)
{
return c >= 'a' && c <= 'z';
}
void has(char *a)
{
int ans = 0;
for(k = 1;k <= 3; ++k)
{
ans = 0;
for(i = 0;i <=lung; ++i)
{
ans *= baz[k];
ans += a[i] - 'a';
ans = tab[ans];
}
an[k][ans] = 1;
}
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
fgets(a,lemax,stdin);
for(i = 1;i <= 30 * mod; ++i)
{
tab[i] = i % mod;
}
while(!feof(stdin))
{
fgets(s,30,stdin);
lung = strlen(s) - 1;
while(!lit(s[lung]))
{
--lung;
}
has(s);
}
++lung;
int prod[10] = {1,1,1,1,1,1,1};
for(k = 1;k <= 3; ++k)
{
for(i = 1;i <= lung; ++i)
{
prod[k] *= baz[k];
prod[k] = tab[prod[k]];
}
}
int n = strlen(a) - 1;
while(!lit(a[n]))
{
--n;
}
for(i = 0;i <= n; ++i)
{
for(k = 1;k <= 3; ++k)
{
hash[k] *= baz[k];
hash[k] = tab[hash[k]];
hash[k] += a[i] - 'a';
if (i >= lung)
{
hash[k] -= prod[k] * (a[i - lung] - 'a');
while (hash[k] < 0) hash[k] += mod;
}
}
if (i >= lung - 1)
{
int sol = 1;
for(k = 1;k <= 3; ++k)
{
sol = min(sol,an[k][hash[k]]);
}
ans += sol;
}
}
printf("%d\n",ans);
return 0;
}