Cod sursa(job #153215)

Utilizator rethosPaicu Alexandru rethos Data 10 martie 2008 11:50:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[MAXN], B[MAXN];
int NA, NB;
int hashA1, hashA2, P1, P2,i;
char match[MAXN];
int main()
{ freopen("strmatch.in", "rt", stdin);
  freopen("strmatch.out", "wt", stdout);
  scanf("%s %s", A, B);
  NA=strlen(A);
  NB=strlen(B);
  P1=P2=1;
  hashA1=hashA2=0;
  for (i=0;i<NA;i++)
	{ hashA1=(hashA1*P+A[i])% MOD1;
	  hashA2=(hashA2*P+A[i])% MOD2;
	  if (i!=0)
	     P1=(P1 * P) % MOD1,
	     P2=(P2 * P) % MOD2;
	}

  if (NA>NB)
	{ printf("0\n");
	  return 0;
	}
  int hash1=0,hash2=0;
  for (i=0;i<NA;i++)
	hash1=(hash1*P+B[i])%MOD1,
	hash2=(hash2*P+B[i])%MOD2;
  int Nr=0;
  if (hash1==hashA1&&hash2==hashA2)
	match[0]=1,Nr++;
  for (i=NA;i<NB;i++)
	{ hash1=((hash1-(B[i-NA]*P1)%MOD1)*P+B[i])%MOD1;
	  hash2=((hash2-(B[i-NA]*P2)%MOD2)*P+B[i])%MOD2;
	  if (hash1==hashA1&&hash2==hashA2)
	  match[i-NA+1]=1,Nr++;
	}
  printf("%d\n", Nr);
  Nr=0;
  for (i=0;i<NB&&Nr<1000;i++)
	if (match[i])
		Nr++,
		printf("%d ", i);
  printf("\n");
  return 0;
}