Cod sursa(job #538460)

Utilizator SadmannCornigeanu Calin Sadmann Data 21 februarie 2011 15:07:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000005
FILE *in,*out;
char A[NMAX],B[NMAX];
int N,M,i,pi[NMAX],pos[1024];

inline int minim(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

void make_prefix()
{
    int 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()
{
    in=fopen("strmatch.in","rt");
    out=fopen("strmatch.out","wt");
    fscanf(in,"%s",A);
    fscanf(in,"%s",B);
    M=strlen(A);
    N=strlen(B);
    int n=0,q=0;
    for(i=M;i;i--)
        A[i]=A[i-1];
    A[0]=' ';
    for(i=N;i;i--)
        B[i]=B[i-1];
    B[0]=' ';

    make_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(out,"%d\n", n);
    for(i=1;i<=minim(n,1000);i++)
        fprintf(out,"%d ",pos[i]);
    fprintf(out,"\n");

    return 0;
}