Cod sursa(job #392257)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 7 februarie 2010 03:10:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#define Nmax 2000000
char A[Nmax],B[Nmax];
int pi[Nmax],pos[1024];
int N,M;

void prefix()
{int q=0,i;pi[1]=0;
  for(i=2;i<=M;i++)
  {while(q && A[q+1]!=B[i])
    q=pi[q];
  if(A[q+1]==B[i])
    ++q;
  pi[i]=q;
  }
}

int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(A,sizeof(A),stdin);
fgets(B,sizeof(B),stdout);
	while((A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')|| (A[M] >= '0' && A[M] <= '9'))
        ++M;
	while((B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')|| (B[N] >= '0' && B[N] <= '9'))
	++N;
int i;
	for(i=M;i>0;i--) A[i]=A[i-1]; A[0]=' ';
	for(i=N;i>0;i--) B[i]=B[i-1]; B[0]=' ';
int q=0,n=0;	
	prefix();
	
	for(i=1;i<=N;i++)
	{	while(q && A[q+1]!=B[i])
			q=pi[q];
		if(q && A[q+1]==B[i])
			++q;
		if(q==M)
		{q=pi[M];
		++n;
		if(n<=1000)
		pos[n]=i-M;
		}
	}
printf("%d\n",n);
if(n>1000)
n=1000;
for(i=1;i<=n;i++)
printf("%d ",pos[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;}