Cod sursa(job #795045)

Utilizator radustn92Radu Stancu radustn92 Data 7 octombrie 2012 15:27:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define MOD1 100007
#define MOD2 100021
#define P 73
#define LMAX 1005
char A[NMAX],B[NMAX];
int sol[LMAX],r;
int n,m,pi[NMAX];
int hash1,hash2,hash11,hash22,P1,P2;
inline int check(char x)
{
	return (x>='0' && x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z') ;
}
void read()
{
	fgets(A+1,NMAX,stdin);
	fgets(B+1,NMAX,stdin);
	while (check(A[n+1])) n++;
	while (check(B[m+1])) m++;
}
void precompute()
{
	int i;
	for (i=1; i<=n; i++)
	{
		hash1 = ( hash1 * P + A[i] ) % MOD1;
		hash2 = ( hash2 * P + A[i] ) % MOD2;
	}
	P1=P2=1;
	for (i=1; i<n; i++)
		P1 = ( P1 * P ) % MOD1, P2 = ( P2 * P ) % MOD2;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void solve()
{
	int i,val;
	for (i=1; i<=n; i++)
	{
		hash11 = ( hash11 * P + B[i] ) % MOD1;
		hash22 = ( hash22 * P + B[i] ) % MOD2;
	}
	if (hash1==hash11 && hash2==hash22)
		sol[++r]=1;
	
	for (i=n+1; i<=m; i++)
	{
		hash11 = hash11 - (P1 * B[i-n]) % MOD1 ;
		if (hash11<0) hash11 += MOD1;
		hash11 = ( hash11 * P + B[i] ) % MOD1;
		
		hash22 = hash22 - (P2 * B[i-n]) % MOD2 ;
		if (hash22<0) hash22 += MOD2;
		hash22 = ( hash22 * P + B[i] ) % MOD2;
		
		if (hash1==hash11 && hash2==hash22)
		{
			r++;
			if (r<=1000)
				sol[r]=i-n+1;
		}
	}
	
	printf("%d\n",r);
	for ( i=1, val= min ( 1000, r) ; i <= val; i++)
		printf("%d ",sol[i]);
	printf("\n");
}
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	read();
	precompute();
	solve();
	return 0;
}