Pagini recente » Cod sursa (job #997667) | Cod sursa (job #1257534) | Cod sursa (job #2449684) | Cod sursa (job #1393720) | Cod sursa (job #2351513)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define NMAX 2000003
#define BAZA 77
#define MOD1 100005
#define MOD2 100023
string A, B;
int N, M;
int cnt, P1 = 1, P2 = 1, cntt;
int Hash1, Hash2, hash1, hash2;
bitset <NMAX> v;
int main (){
fin >> A >> B;
N = A.size ();
M = B.size ();
for (int i = 0; i < N; i ++){
Hash1 = (Hash1 * BAZA + A [i]) % MOD1;
Hash2 = (Hash2 * BAZA + A [i]) % MOD2;
if (i != 0)P1 = (P1 * BAZA) % MOD1, P2 = (P2 * BAZA) % MOD2;
}
if (N > M)return fout << 0, 0;
for (int i = 0; i < N; i ++)
hash1 = (hash1 * BAZA + B [i]) % MOD1,
hash2 = (hash2 * BAZA + B [i]) % MOD2;
if (hash1 == Hash1 && hash2 == Hash2)
v [0] = 1, cnt ++;
for (int i = N; i < M; i ++){
hash1 = ((hash1 - (B [i - N] * P1) % MOD1 + MOD1) * BAZA + B [i]) % MOD1;
hash2 = ((hash2 - (B [i - N] * P2) % MOD2 + MOD2) * BAZA + B [i]) % MOD2;
if (hash1 == Hash1 && hash2 == Hash2)
v [i - N + 1] = 1, cnt ++;
}
fout << cnt << '\n';
for (int i = 0; i < M && cntt < 1000; i ++)
if (v [i])cntt ++, fout << i << " ";
return 0;
}