Cod sursa(job #629628)

Utilizator lianaliana tucar liana Data 3 noiembrie 2011 16:20:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>
#define baza 54
#define lmax 2000005
#define p1 666013
using namespace std;
long  nra[3], nrb[3], k, i, la, lb, rez, blan[3], x, vrez[1005], p;
bool ok, eg;
char a[lmax], b[lmax];

long num(char q)
{
	if ((q>='a')&&(q<='z'))
		return q-'a';
	if ((q>='A')&&(q<='Z'))
		return q-'A'+27;
	return q-'0'+54;
}

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(b);	gets(a);
	la=strlen(a);	lb=strlen(b);
	blan[0]=1;	blan[1]=1;
	for (p=666013;p<=666014;p++)
	{
		for (i=1;i<=lb-1;i++)
		blan[p-p1]=(blan[p-p1]*baza)%p;
		for (i=0;i<lb;i++)
		{
			nra[p-p1]=(nra[p-p1]*baza+num(a[i]))%p;
			nrb[p-p1]=(nrb[p-p1]*baza+num(b[i]))%p;
		}
	}
	i=0;
	if ((nra[1]==nrb[1])&&(nra[0]==nrb[0]))
		vrez[++rez]=0;	
	for (i=1;i<=la-lb;i++)
	{
		eg=1;
		for (p=666013;p<=666014;p++)
		{
			nra[p-p1]=(nra[p-p1]-blan[p-p1]*num(a[i-1]))%p;
			nra[p-p1]=(nra[p-p1]*baza)%p;
			nra[p-p1]+=num(a[i+lb-1]);
			nra[p-p1]=(nra[p-p1]+p)%p;
			if (nra[p-p1]!=nrb[p-p1])
				eg=0;
		}
		rez+=eg;
		if ((rez<=1000) &&(eg))
			vrez[rez]=i;
	}
	printf("%ld\n",rez);
	if (rez>1000)
		rez=1000;
	for (i=1;i<=rez;i++)
		printf("%ld ",vrez[i]);
	return 0;
}