Cod sursa(job #2950979)

Utilizator STEFANBUSOIStefan Busoi STEFANBUSOI Data 4 decembrie 2022 23:55:24
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define MAXN 2000001

#define P 73
#define MOD 100123456789
using namespace std;
char A[MAXN], B[MAXN];
long long NA, NB;

long long hashA, P1;

char match[MAXN];

void citire(){
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);

	scanf("%s %s", A, B);
	NA = strlen(A);
	NB = strlen(B);
}

void afisare(int Nr){
    printf("%d\n", Nr);

	Nr = 0;
	for (int i = 0; i < NB && Nr < 1000; i++)
		if (match[i])
			Nr++,
			printf("%d ", i);
	printf("\n");
}

int main()
{

    citire();
	P1= 1;
	hashA = 0;
	for (int i = 0; i < NA; i++)
	{
		hashA = (hashA * P + A[i]) % MOD;

		if (i != 0)
			P1 = (P1 * P) % MOD;
	}

	if (NA > NB)///if first string is larger
	{
		printf("0\n");
		return 0;
	}
	long long hash1 = 0;
	for (int i = 0; i < NA; i++){
		hash1 = (hash1 * P + B[i]) % MOD;
	}
	int Nr = 0;
	if (hash1 == hashA )
		match[0] = 1, Nr++;

	for (int i = NA; i < NB; i++)
	{
		hash1 = ((hash1 - (B[i - NA] * P1) % MOD) * P + B[i]) % MOD;
		if (hash1 == hashA)
			match[ i - NA + 1 ] = 1, Nr++;
	}

    afisare(Nr);
	return 0;
}