Cod sursa(job #2351518)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 22 februarie 2019 14:47:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define NMAX 2000003
#define BAZA 77
#define MOD1 100007
#define MOD2 100021
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;
}