Cod sursa(job #428189)

Utilizator ooctavTuchila Octavian ooctav Data 28 martie 2010 23:09:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define MMAX 2000005
#define MOD1 100003
#define MOD2 100019
#define P 73
int P1 = 1, P2 = 1;

int URM[MMAX];
char A[NMAX],B[MMAX];
int N, M;
int amod1, amod2;
int bmod1, bmod2;
int NR = 0;
int poz[NMAX];

void citire()
{
	scanf("%s%s",A,B);
	N = strlen(A);
	M = strlen(B);
}

void obt()
{
	for(int i = 0 ; i < N ; i++)
	{
		amod1 = (amod1 * P + A[i]) % MOD1;
		amod2 = (amod2 * P + A[i]) % MOD2;
		bmod1 = (bmod1 * P + B[i]) % MOD1;
		bmod2 = (bmod2 * P + B[i]) % MOD2;
		if(i)
		{
			P1 = (P1 * P) % MOD1;
			P2 = (P2 * P) % MOD2;
		}
	}
	if(amod1 == bmod1 && amod2 == bmod2)
		poz[++NR] = 0;
}

void RK()
{
	for(int i = N ; i < M ; i++)
	{
		bmod1 = ((bmod1 - (B[i - N] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		bmod2 = ((bmod2 - (B[i - N] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
		if(amod1 == bmod1 && amod2 == bmod2)
			poz[++NR] = i - N + 1;
	}
}

void scrie()
{
	printf("%d\n",NR);
	for(int i = 1 ; i <=  NR ; i++)
		printf("%d ",poz[i]);
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	citire();
	obt();
	RK();
	scrie();
	
	return 0;
	
}