Cod sursa(job #1174340)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 22 aprilie 2014 16:37:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <vector>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <fstream>

using namespace std;

#define ONLINE_JUDGE

#define MOD1 666013
#define MOD2 666019
#define base 73

#define pb push_back
#define ENTER fprintf(output, "\n");
#define OKK fprintf(output, "ok!\n");
#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define LL long long

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

int hashA1, hashA2, hashB1, hashB2;
char A[2000001], B[2000001];
int fact1 = 1, fact2 = 1, cnt;
vi ans;

int main() {
#ifdef ONLINE_JUDGE
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
#else
	freopen("input.txt", "r", stdin);
#endif
	int lgA, lgB, i;
	
	scanf("%s %s", A, B);
	
	lgA = strlen(A);
	lgB = strlen(B);
	
	hashA1 = hashA2 = A[0];
	hashB1 = hashB2 = B[0];
	
	for (i = 1; i < lgA; ++i) {
		fact1 = (fact1 * base) % MOD1;
		fact2 = (fact2 * base) % MOD2;
		
		hashA1 = (hashA1 * base + A[i]) % MOD1;
		hashA2 = (hashA2 * base + A[i]) % MOD2;
		
		hashB1 = (hashB1 * base + B[i]) % MOD1;
		hashB2 = (hashB2 * base + B[i]) % MOD2;
	}
	
	if (hashA1 == hashB1 && hashA2 == hashB2) {
		ans.pb(0); ++cnt;
	}
	
	for (i = lgA; i < lgB; ++i) {
		hashB1 = ((hashB1 + MOD1 - (B[i - lgA] * fact1) % MOD1) * base + B[i]) % MOD1;
		hashB2 = ((hashB2 + MOD2 - (B[i - lgA] * fact2) % MOD2) * base + B[i]) % MOD2;
		
		if (hashA1 == hashB1 && hashA2 == hashB2) {
			++cnt;
			if (cnt < 1001) {
				ans.pb(i - lgA + 1);
			}
		}
	} 
	
	printf("%d\n", cnt);
	for (auto &x: ans) {
		printf("%d ", x);
	}
	
	return 0;
}