Cod sursa(job #192899)

Utilizator savimSerban Andrei Stan savim Data 1 iunie 2008 11:04:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>

#define ui unsigned long int
#define maxl 200010
#define baz 65

ui i,j,k,n,m,val,put,nr;
char A[maxl],B[maxl],trans[maxl];
int poz[maxl],abc[256];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    scanf("%s",A+1);A[0]=' ';
    n=strlen(A)-1;
    scanf("%s",B+1);B[0]=' ';
    m=strlen(B)-1;
    
	k=0;
	for (i=48; i<=57; i++) abc[i]=++k;
	for (i=65; i<=90; i++) abc[i]=++k;
	for (i=97; i<=122; i++) abc[i]=++k;

	k=0;
	for (i=1; i<=n-1; i++)
	{
		val=val*baz+abc[A[i]];
		k=k*baz+abc[B[i]];
	}
	val=val*baz+abc[A[n]];

	put=1;
	for (i=1; i<=n; i++) put*=baz;

	B[0]='*';abc[42]=0;
	for (i=n; i<=m; i++)
	{
		  k=k*baz+abc[B[i]];
		  k-=put*(abc[B[i-n]]);

		  if (k==val)
			 poz[++nr]=i-n;
	}

	printf("%d\n",nr);
    if (nr>1000) nr=1000;
	for (i=1; i<=nr; i++)
		printf("%d ",poz[i]);
    
    return 0;    
}