Cod sursa(job #591027)

Utilizator Catah15Catalin Haidau Catah15 Data 21 mai 2011 19:34:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <vector>

using namespace std;

#define maxN 2000005
#define baza 73
#define MOD1 100007
#define MOD2 100021 
#define PB push_back


char A[maxN], B[maxN];
bool match[maxN];
int hashA1, hashA2, hashB1, hashB2;
int baza1 = 1, baza2 = 1;
vector <int> sol;
	

int main()
{
	freopen ("strmatch.in", "r", stdin);
	freopen ("strmatch.out", "w", stdout);
	
	scanf ("%s %s", A, B);
	
	int lengA = strlen (A);
	int lengB = strlen (B);
	
	
	if (lengA > lengB)
	{
		printf ("0");
		return 0;
	}


	for (int i = 0; i < lengA; ++ i)
	{
		hashA1 = (hashA1 * baza + A[i]) % MOD1;
		hashA2 = (hashA2 * baza + A[i]) % MOD2;
		
		hashB1 = (hashB1 * baza + B[i]) % MOD1;
		hashB2 = (hashB2 * baza + B[i]) % MOD2;
		
		if (i)
		{
			baza1 = (baza * baza1) % MOD1;
			baza2 = (baza * baza2) % MOD2;
		}
	}

	
	if (hashA1 == hashB1 && hashA2 == hashB2) sol.PB (0);
	
	
	for (int i = lengA; i < lengB; ++ i)
	{
		hashB1 = ((hashB1 - (B[i - lengA] * baza1) % MOD1 + MOD1) * baza + B[i]) % MOD1;
		hashB2 = ((hashB2 - (B[i - lengA] * baza2) % MOD2 + MOD2) * baza + B[i]) % MOD2;
		
		if (hashA1 == hashB1 && hashA2 == hashB2) sol.PB (i - lengA + 1);
	}
	
	
	printf ("%d \n", sol.size());
	
	for (unsigned int i = 0; i < sol.size() && i < 1000; ++ i) 
		printf ("%d ", sol[i]);
	
	
	return 0;
}