Cod sursa(job #161368)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 17 martie 2008 22:29:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000001

char P[NMAX],T[NMAX];
int Pi[NMAX],R[1000],pi,r;

void prefix(char *P, int p)
{
    int k=-1;
    for (Pi[0]=-1,pi=1;pi<p;pi++)
    {
        while (k+1 && P[k+1]!=P[pi] ) k=Pi[k];
        k+=(int)(P[k+1]==P[pi]);
        Pi[pi]=k;
    }
}

void KMP(char *P, int p, char *T, int t)
{
    int q=-1,i;
    for ( i=0;i<t;i++)
    {
        while (q+1&&P[q+1]!=T[i]) q=Pi[q];
        q+=(int)(P[q+1]==T[i]);
        if (q==p-1)
        {
            r++;
            if (r<1001) R[r-1]=i-p+1;
        }
    }
}

int main ()
{
    int i;

    fscanf (fopen (FIN,"r") , "%s\n%s\n" , P , T);
    int p=strlen(P),t=strlen(T);
    prefix(P,p);
    KMP(P,p,T,t);
    freopen (FOUT , "w" , stdout);
    printf ( "%d\n" , r );p=0;if(r>1000) r=1000;
    for ( p=0 ; p<r-1 ; p++ )
        printf ( "%d " , R[p] );
    if (r) printf ( "%d\n" , R[p] );

    fclose ( stdout );
    return 0;
}