Cod sursa(job #186262)

Utilizator adrian69adrian horia adrian69 Data 27 aprilie 2008 03:27:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<string>
#define nmax 2000005
#define min(a, b) ((a < b) ? a : b)  
int N,M;
char A[nmax],B[nmax];
int pi[nmax],pos[1024];
void prefix()
{
	int i,q=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()
{FILE *f,*g;
	int i,q=0,n=0;
 f=fopen("strmatch.in","r");
 g=fopen("strmatch.out","w");
 fgets(A,sizeof(A),f);
 fgets(B,sizeof(B),f);
 M=strlen(A);
 M--;
 N=strlen(B);
 N--;
     for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';  
     for (i = N; i; --i) B[i] = B[i-1]; B[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;	
		}	
   	} 
 
 fprintf(g,"%d\n",n);
 for(i=1;i<=min(n,1000);++i)
    fprintf(g,"%d ",pos[i]);
    fprintf(g,"\n");
 fclose(f);
 fclose(g);
 return 0;
}