Cod sursa(job #415146)

Utilizator OdinSandu Bogdan-Mihai Odin Data 10 martie 2010 22:42:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<string.h>
#define min(a,b) a < b ? a : b
#define MAX 2000001
#define p 73
#define m1 100007
#define m2 100021
char s1[MAX],s2[MAX];
int n1,n2,p1=1,p2=1,h1s1,h1s2,h2s1,h2s2,i,sol[MAX],k,t;
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",&s1,&s2);
	n1=strlen(s1);
	n2=strlen(s2);
	for(i=0;i<n1;i++)
	{
		h1s1=(h1s1*p+s1[i])%m1;
		h2s1=(h2s1*p+s1[i])%m2;
		if(i)
		{
		p1=(p1*p)%m1;
		p2=(p2*p)%m2;
		}
	}
	for(i=0;i<n2;i++)
	{
		if(i<n1)
		{
			h1s2=(h1s2*p+s2[i])%m1;
			h2s2=(h2s2*p+s2[i])%m2;
		}
		else
		{
			h1s2=((h1s2-(s2[i-n1]*p1)%m1+m1)*p+s2[i])%m1;
			h2s2=((h2s2-(s2[i-n1]*p2)%m2+m2)*p+s2[i])%m2;
		}
		if(h1s1==h1s2&&h2s1==h2s2)
		{
			sol[k]=i-n1+1;
			k++;
		}
	}
	printf("%d\n",k);
	t=min(k,1000);
	for(i=0;i<t;i++)
		printf("%d ",sol[i]);
	return 0;
}