Pagini recente » Cod sursa (job #1982074) | Cod sursa (job #1351479) | Cod sursa (job #1890184) | Cod sursa (job #3227637) | Cod sursa (job #2015802)
#include <bits/stdc++.h>
#define MOD1 10007
#define MOD2 666013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
vector<int>pos;
const int base1 = 27, base2 = 29;
int hash1, hash2, HASH1, HASH2, answ;
int main()
{
fin >> A; fin.get(); fin >> B;
pos.resize(B.length() + 1, 0);
int lengthA = A.length();
int Pow1 = 1, Pow2 = 1;
for (int i = 0; i < lengthA; ++i)
{
hash1 = (hash1 * base1 + A[i]) % MOD1;
hash2 = (hash2 * base2 + A[i]) % MOD2;
if (i)
Pow1 = (Pow1 * base1) % MOD1, Pow2 = (Pow2 * base2) % MOD2;
}
if (lengthA > B.length())
{
fout << 0 << "\n";
return 0;
}
for (int i = 0; i < A.length();)
HASH1 = (HASH1 * base1 + B[i]) % MOD1, HASH2 = (HASH2 * base2 + B[i++]) % MOD2;
if (hash1 == HASH1 && hash2 == HASH2)
++answ, pos[0] = 1;
for (int i = lengthA; i < B.length(); ++i)
{
HASH1 = ((HASH1 - (B[i - lengthA] * Pow1) % MOD1 + MOD1) * base1 + B[i]) % MOD1;
HASH2 = ((HASH2 - (B[i - lengthA] * Pow2) % MOD2 + MOD2) * base2 + B[i]) % MOD2;
if (hash1 == HASH1 && hash2 == HASH2)
++answ, pos[i - lengthA + 1] = 1;
}
fout << answ << "\n";
int cnt = 0;
for (int i = 0; i < B[i] && cnt < 1000; ++i)
if (pos[i])
fout << i << " ", cnt++;
return 0;
}