Cod sursa(job #392272)

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

void prefix(void)
{int q=0,i=0;
  for(i=2,pi[1]=0;i<=M;++i)
  {while(q && A[q+1]!=A[i])
    q=pi[q];
  if(A[q+1]==A[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),stdin);
	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(A[q+1]==B[i])
			++q;
		if(q==M)
		{q=pi[M];
		++n;
		if(n<=1000)
		pos[n]=i-M;
		}
	}
printf("%d %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;}