Cod sursa(job #631712)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 9 noiembrie 2011 17:58:20
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
#include<cstring>
#define Mod 666013
#define Mod2 10003

using namespace std;

int i,nr,v1,v2,poz[2000001],n,m,p1,p2,s1,s2;
char a[2000002],b[2000002];
int main()
{
	nr=0;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%d",&n);
	gets(a+1);
	m=strlen(a+1);
	gets(b+1);
	n=strlen(b+1);
	p1=1;
	p2=1;
	s1=0;
	s2=0;
	v1=0;
	v2=0;
	for (i=1;i<=m;i++)
	{
		s1=(s1*137+a[i])%Mod;
		s2=(s1*157+a[i])%Mod2;
		v1=(v1*137+b[i])%Mod;
		v2=(v2*157+b[i])%Mod2;
		if (i<m)p1=(p1*137)%Mod;
		if (i<m)p2=(p2*157)%Mod2;
	}
	if(v1==s1&&v2==s2)
		{
			nr++;
			poz[nr]=i-m;
		}
	for (i=m+1;i<=n;i++)
	{
		v1=(((v1-b[i-m]*p1)%Mod+Mod)*137+b[i])%Mod;
		v2=(((v2-b[i-m]*p2)%Mod2+Mod2)*157+b[i])%Mod2;
		if(v1==s1&&v2==s2)
		{
			nr++;
			poz[nr]=i-m;
		}
	}
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	for (i=1;i<=nr;i++)
	{
		printf("%d ",poz[i]);
	}
	return 0;
}