Nu aveti permisiuni pentru a descarca fisierul grader_test3.ok
Cod sursa(job #2027620)
| Utilizator | Data | 26 septembrie 2017 14:04:26 | |
|---|---|---|---|
| Problema | Abc2 | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.79 kb |
# include <bits/stdc++.h>
# define MOD1 666013
# define MOD2 2017
# define ll long long
using namespace std;
const int len_max = 26 + 5, text_max = 1e7 + 5;
vector <ll> Hash[MOD1];
char text[text_max], s[len_max];
int n, m, ans, pw[len_max];
void powers()
{
pw[0] = 1;
for (int i = 1; i <= len_max; ++i)
pw[i] = pw[i - 1] * 27;
}
int Search(ll key, ll val)
{
for (auto &it: Hash[key])
if (it == val) return 1;
return 0;
}
int main ()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
gets(text + 1), n = strlen(text + 1);
powers();
do
{ ll hash_a1 = 0, hash_a2 = 0;
gets(s + 1), m = strlen(s + 1);
for (int i = 1; i <= m; ++i)
hash_a1 += (s[i] * pw[m - i + 1]) % MOD1, hash_a2 += (s[i] * pw[m - i + 1]) % MOD2;
hash_a1 %= MOD1, hash_a2 %= MOD2;
Hash[hash_a1].push_back(hash_a2);
}
while (!feof(stdin));
ll hash_b1 = 0, hash_b2 = 0;
for (int i = 1; i <= n; ++i)
{
if (i <= m) {
hash_b1 += (pw[m - i + 1] * text[i]) % MOD1, hash_b1 %= MOD1;
hash_b2 += (pw[m - i + 1] * text[i]) % MOD2, hash_b2 %= MOD2;
if (i < m) continue;
}
if (i > m) {
hash_b1 -= (pw[m] * text[i - m]) % MOD1;
hash_b1 %= MOD1, hash_b1 += MOD1, hash_b1 %= MOD1;
hash_b2 -= (pw[m] * text[i - m]) % MOD2;
hash_b2 %= MOD2, hash_b2 += MOD2, hash_b2 %= MOD2;
hash_b1 +=(text[i]) % MOD1, hash_b2 += (text[i]) % MOD2;
hash_b1 *= pw[1] , hash_b1 %= MOD1;
hash_b2 *= pw[1], hash_b2 %= MOD2;
}
ans += Search(hash_b1, hash_b2);
}
printf("%d\n", ans);
return 0;
}
