Cod sursa(job #831606)

Utilizator lianaliana tucar liana Data 8 decembrie 2012 20:33:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<cstring>
using namespace std;
#define p1 666013
#define p2 666023
#define baz 130
#define lgmax 2000005
long nra1, nra2, nrb1, nrb2, rez, v[1005], pbaz1, pbaz2, i, la, lb;
char a[lgmax], b[lgmax];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",a);	scanf("%s",b);
	la=strlen(a);	lb=strlen(b);
	if (la<=lb)
	{
		for (i=0;i<la;i++)
		{	
			nra1=(nra1*baz+a[i])%p1;	nra2=(nra2*baz+a[i])%p2;	
			nrb1=(nrb1*baz+b[i])%p1;	nrb2=(nrb2*baz+b[i])%p2;	
		}
		if ((nra1==nrb1)&&(nra2==nrb2))
			v[++rez]=0;	
		
		pbaz1=pbaz2=1;
		for (i=1;i<=la-1;i++)
		{	pbaz1=(pbaz1*baz)%p1;	pbaz2=(pbaz2*baz)%p2;		}
		
		
		for	(i=la;i<lb;i++)
		{
			nrb1=nrb1-(b[i-la]*pbaz1)%p1;
			if (nrb1<0)
				nrb1+=p1;
			nrb1=(nrb1*baz+b[i])%p1;
			
			nrb2=nrb2-(b[i-la]*pbaz2)%p2;
			if (nrb2<0)
				nrb2+=p2;
			nrb2=(nrb2*baz+b[i])%p2;
			
			if ((nra1==nrb1)&&(nra2=nrb2))
			{
				rez++;
				if (rez<=1000)
					v[rez]=i-la+1;
			}
		}
	
		printf("%ld\n",rez);
		for (i=1;i<=rez;i++)
		{
			printf("%ld ",v[i]);
			if (i==1000)
				break;
		}
	}	
	else
		printf("0");
	return 0;
}