Cod sursa(job #169914)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 2 aprilie 2008 10:58:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <string.h>
#define K 2000009
char A[K],B[K];
int pi[K],poz[1001];
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<=1000) poz[n]=i-M;     
        }
	}
	printf("%d\n", n);
	for(int i=1;i<=minim(n,1000);++i)
		printf("%d ", poz[i]);
}
int main()
{
	scan();
	solve();
	return 0;
}