Pagini recente » Cod sursa (job #2169997) | Cod sursa (job #1494345) | Cod sursa (job #1226664) | Cod sursa (job #305744) | Cod sursa (job #2261179)
#include <fstream>
#include <cstring>
using namespace std;
const int MOD1 = 777013;
const int MOD2 = 123457;
const int HASH1 = 101;
const int HASH2 = 23;
const int NMAX = 1e7 + 10;
const int MMAX = 5e4 + 10;
char s[NMAX], a[MMAX];
bool mp1[MOD1], mp2[MOD2];
int n, m, val1 = 1, val2 = 1;
inline int RepairMod(long long x, const int &MOD)
{
while (x > MOD)
x -= MOD;
while (x < 0)
x += MOD;
return x;
}
int main()
{
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> (s + 1);
n = strlen(s + 1);
int hashCode1, hashCode2;
while (fin >> (a + 1))
{
if (m == 0)
{
m = strlen(a + 1);
for (int j = 1;j <= m;++j)
{
val1 = RepairMod(val1 * HASH1, MOD1);
val2 = RepairMod(val2 * HASH2, MOD2);
}
}
hashCode1 = hashCode2 = 0;
for (int j = 1;j <= m;++j)
{
hashCode1 = RepairMod(1LL * hashCode1 * HASH1 + (a[j] - 'a' + 1), MOD1);
hashCode2 = RepairMod(1LL * hashCode2 * HASH2 + (a[j] - 'a' + 1), MOD2);
}
mp1[hashCode1] = true;
mp2[hashCode2] = true;
}
hashCode1 = hashCode2 = 0;
int cnt = 0;
for (int i = 1;i <= n;++i)
{
hashCode1 = RepairMod(1LL * hashCode1 * HASH1 + (s[i] - 'a' + 1), MOD1);
hashCode2 = RepairMod(1LL * hashCode2 * HASH2 + (s[i] - 'a' + 1), MOD2);
if (i > m)
{
hashCode1 = RepairMod(1LL * hashCode1 - 1LL * (s[i - m] - 'a' + 1) * val1, MOD1);
hashCode2 = RepairMod(1LL * hashCode2 - 1LL * (s[i - m] - 'a' + 1) * val2, MOD2);
}
if (i >= m && mp1[hashCode1] == true && mp2[hashCode2] == true)
++cnt;
}
fout << cnt << "\n";
fin.close();
fout.close();
return 0;
}