Cod sursa(job #169906)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 2 aprilie 2008 10:52:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <string.h>
#define K 2000009
#define lmax 1000
char A[K],B[K];
int pi[K],poz[lmax+1];
int M,N;
inline int minim(int x,int y){
	if(x<y) 
		return x;
	return y;
}	
void scan()
{
	freopen("strmatch.in", "r",stdin);
	freopen("strmatch.out", "w",stdout);
	gets(A+1); gets(B+1);
	M=strlen(A+1); N=strlen(B+1);
}
void make_prefix()
{
	int i,q=0;
	for(pi[1]=0,i=2 ;i<= M ;++i)  
    {  
        while ( q && A[q+1]!=A[i] )  
            q = pi[q];  
        if (A[q+1] == A[i])  
            ++q;  
        pi[i]=q;  
    }  
}  
void solve()
{
	int n=0,q=0;
	make_prefix();
	for(int 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<=lmax)  
                poz[n]=i-M;     
        }
	}
	printf("%d\n", n);
	for(int i=1;i<=minim(n,lmax);++i)
		printf("%d ", poz[i]);
}
int main()
{
	scan();
	solve();
	return 0;
}