Cod sursa(job #629492)

Utilizator lianaliana tucar liana Data 3 noiembrie 2011 14:08:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 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, 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 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=a[i]-'A'+26;
		if ((a[i]>='a')&&(a[i]<='z'))
			x=a[i]-'a';
		nra=(nra*baza+x)%p;
		x=b[i]-'A'+26;
		if ((b[i]>='a')&&(b[i]<='z'))
			x=b[i]-'a';
		nrb=(nrb*baza+x)%p;
	}
	i=0;
	if (nra==nrb)
		verificare();
	for (i=1;i<=la-lb;i++)
	{
		x=a[i-1]-'A'+26;
		if ((a[i-1]>='a')&&(a[i-1]<='z'))
			x=a[i-1]-'a';
		nra=(nra-blan*x)%p;
		nra=(nra*baza)%p;
		x=a[i+lb-1]-'A'+26;
		if ((a[i+lb-1]>='a')&&(a[i+lb-1]<='z'))
			x=a[i+lb-1]-'a';	
		nra+=x;
		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;
}