Cod sursa(job #428195)

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

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

void citire()
{
	gets(A);
	gets(B);
	M = strlen(A);
	while(!A[M - 1] || A[M - 1] == '\n' || A[M - 1] == EOF)
		M--;
	N = strlen(B);
	while(!B[N - 1] || B[N - 1] == '\n' || B[N - 1] == EOF)
		N--;
}

void obt()
{
	for(int i = 0 ; i < M ; 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 = M ; i < N ; i++)
	{
		bmod1 = ((bmod1 - (B[i - M] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		bmod2 = ((bmod2 - (B[i - M] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
		if(amod1 == bmod1 && amod2 == bmod2)
			poz[++NR] = i - M + 1;
	}
}

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

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