Cod sursa(job #381533)

Utilizator allynaAlina S allyna Data 10 ianuarie 2010 21:01:58
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD 100007
char p[MAXN],t[MAXN],n,m,v[MAXN];
int hashp,q,num,hash,i;
int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s",p,t);
	n=strlen(p);
	m=strlen(t);
	q=1;
	hashp=0;
	for (i=0;i<n;i++)
	{
		hashp=(hashp*P+p[i])%MOD;
		if (i!=0)
			q=(q*P)%MOD;
	}
	if (n>m)
	{
		printf("0\n");
		return 0;
	}
	for (i=0;i<n;i++)
		hash=(hash*P+t[i])%MOD;
	if (hash==hashp)
		v[0]=1, num++;
	for (i=n;i<m;i++)
	{
		hash=((hash-(t[i-n]*q)%MOD+MOD)*P+t[i])%MOD;
		if (hash==hashp)
			v[i-n+1]=1, num++;
	}
	printf("%d\n",num);
	num=0;
	for (i=0;i<m && num<1000;i++)
		if (v[i])
			num++,
			printf("%d ",i);
	printf("\n");
	return 0;
}