Cod sursa(job #629530)

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

void verificare()
{
	ok=1;
	for (k=0;(k<lb&&ok);k++)
		ok=(b[k]==a[i+k]);
	rez+=ok;
	if ((rez<=1000) &&(ok))
		vrez[rez]=i;
}

long  put(long k)
{
	long  pj;
	if (k==0)
		return 1;
	pj=put(k/2);
	if (k%2==0)
		return (pj*pj)%p;
	return (((pj*pj)%p)*baza)%p;
}

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=put(lb-1);
	for (i=0;i<lb;i++)
	{
		nra=(nra*baza+num(a[i]))%p;
		nrb=(nrb*baza+num(b[i]))%p;
	}
	i=0;
	if (nra==nrb)
		verificare();
	for (i=1;i<=la-lb;i++)
	{
		nra=(nra-blan*num(a[i-1]))%p;
		nra=(nra*baza)%p;
		nra+=num(a[i+lb-1]);
		nra=(nra+p)%p;
		if (nra==nrb)
			verificare();
	}
	printf("%ld\n",rez);
	if (rez>1000)
		rez=1000;
	for (i=1;i<=rez;i++)
		printf("%ld ",vrez[i]);
	return 0;
}