Cod sursa(job #401189)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 22 februarie 2010 16:13:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#include<string.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
#define Nmax 2000010
using namespace std;

int P1,P2,HA1,HA2,HB1,HB2,i,A,B,sol,poz[1010];
char a[Nmax],b[Nmax];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	scanf("%s",b+1);
	scanf("%s",a+1);
	
	A=strlen(a+1);
	B=strlen(b+1);
	
	P1=P2=1;
	
	if(B>A) {printf("0"); return 0;}
	
	for(i=1;i<=B;i++)
	{
		HB1 = ( HB1 * P + b[i] ) % MOD1;
		HB2 = ( HB2 * P + b[i] ) % MOD2;
		
		if(i>1)
		{
			P1 = ( P1 * P ) % MOD1;
			P2 = ( P2 * P ) % MOD2;
		}
	}
	
	for(i=1;i<=B;i++)
	{
		HA1 = ( HA1 * P + a[i] ) % MOD1;
		HA2 = ( HA2 * P + a[i] ) % MOD2;
	}
	if(HA1==HB1 && HA2==HB2) sol++;
	
	for(; i<=A; i++)
	{
		HA1 =( ( HA1 - ( a[i-B] * P1 ) % MOD1 + MOD1 ) * P + a[i] ) % MOD1;
		HA2 =( ( HA2 - ( a[i-B] * P2 ) % MOD2 + MOD2 ) * P + a[i] ) % MOD2;
		
		if(HA1==HB1 && HA2==HB2) 
		{
			sol++;
			if(sol<=1000)
				poz[sol]=i-B;
		}
	}
	
	printf("%d\n",sol);
	if(sol>1000) sol=1000;
	for(i=1;i<=sol;i++)
		printf("%d ",poz[i]);
	return 0;
}