Cod sursa(job #236617)

Utilizator luk17Luca Bogdan luk17 Data 28 decembrie 2008 00:11:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000001
char a[NMAX],b[NMAX];
int n,m,lung=0;
int sol[1001];
long baza[NMAX],hasha=0,hashb=0,hashc=0,hashd=0,baza2[NMAX];

void RK()
{
	int i;
	baza[0]=1;
	baza2[0]=1;
	for(i=1;i<m;i++)
	{
		baza[i]=(baza[i-1]*32)%100007;
		baza2[i]=(baza2[i-1]*73)%100021;
	}
	hasha=hashb=0;
	for(i=0;i<m;i++)
	{
		hasha=(hasha+a[i]*baza[m-i-1])%100007;
		hashb=(hashb+b[i]*baza[m-i-1])%100007;
		hashc=(hashc+a[i]*baza2[m-i-1])%100021;
		hashd=(hashd+b[i]*baza2[m-i-1])%100021;
	}

	if(hasha==hashb&&hashc==hashd)sol[++lung]=0;
	
	for(i=1;i<n-m+1;i++)
	{
		hashb=(hashb-(b[i-1]*baza[m-1])%100007+100007)%100007;
		hashb=(hashb*32+b[i+m-1])%100007;
		hashd=(hashd-(b[i-1]*baza2[m-1])%100021+100021)%100021;
		hashd=(hashd*73+b[i+m-1])%100021;
		if((hasha==hashb)&&hashc==hashd)
			if(n>1000&&lung>1000)
				lung++;
			else
				sol[++lung]=i;
			
	}
	printf("%d\n",lung);
	for(i=1;i<=lung&&i<=1000;i++)
		printf("%d ", sol[i]);
}
int main()
{
	

	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
		scanf("%s\n",a);
		scanf("%s",b);
		m=strlen(a);
		n=strlen(b);

	RK();
	

return 0;
}