Cod sursa(job #629466)

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

long num(char a)
{
	if ((a>='a')&&(a<='z'))
		return a-'a';
	return x=a-'A'+26;
}

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 long put(long k)
{
	long 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;
}

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++)
	{
		x=num(a[i]);
		nra=(nra*baza+x)%p;
		x=num(b[i]);
		nrb=(nrb*baza+x)%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);
	for (i=1;i<=rez;i++)
		printf("%ld ",vrez[i]);
	return 0;
}