Cod sursa(job #2985051)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 25 februarie 2023 16:38:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#include <string>

FILE *fin, *fout;

const int DIM = 2e6;
const int P1 = 67;
const int P2 = 61;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;

int N, M, cnt;
char a[DIM + 2], b[DIM + 2];
int value[256];
std :: vector<int>ans;

int hash_a1, hash_a2, hash_b1, hash_b2;

int main() {
	fin = fopen("strmatch.in", "r");
	fout = fopen("strmatch.out", "w");

	fscanf(fin, "%s %s", a, b);

	N = strlen(a);
	M = strlen(b);

	if(N > M) {
		fprintf(fout, "0\n");
		return 0;
	}

	for(int i = 'A'; i <= 'Z'; i++) {
		value[i] = i - 'A';
	}
	for(int i = 'a'; i <= 'z'; i++) {
		value[i] = i - 'a' + 26;
	}
	for(int i = '0'; i <= '9'; i++) {
		value[i] = i - '0' + 52;
	}

	int p1 = 1, p2 = 1;

	for(int i = 0; i < N; i++) {
		hash_a1 = ((long long)P1 * hash_a1 % MOD1 + value[a[i]]) % MOD1;
		hash_a2 = ((long long)P2 * hash_a2 % MOD2 + value[a[i]]) % MOD2;

		if(i != N - 1) {
			p1 = (long long)p1 * P1 % MOD1;
			p2 = (long long)p2 * P2 % MOD2;
		}
	}

	for(int i = 0; i < N; i++) {
		hash_b1 = ((long long)P1 * hash_b1 % MOD1 + value[b[i]]) % MOD1;
		hash_b2 = ((long long)P2 * hash_b2 % MOD2 + value[b[i]]) % MOD2;
	}

	if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
		cnt = 1;
		ans.push_back(0);
	}

	for(int i = N; i < M; i++) {
		hash_b1 = ((long long)hash_b1 - (long long)value[b[i - N]] * p1 % MOD1 + MOD1) % MOD1;
		hash_b2 = ((long long)hash_b2 - (long long)value[b[i - N]] * p2 % MOD2 + MOD2) % MOD2;

		hash_b1 = ((long long)hash_b1 * P1 % MOD1 + value[b[i]]) % MOD1;
		hash_b2 = ((long long)hash_b2 * P2 % MOD2 + value[b[i]]) % MOD2;

		if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
			if(++cnt <= 1000) {
				ans.push_back(i - N + 1);
			}
		}
	}

	fprintf(fout, "%d\n", cnt);
	for(int i = 0; i < ans.size(); i++) {
		fprintf(fout, "%d ", ans[i]);
	}

	fclose(fin);
	fclose(fout);
	return 0;
}