Cod sursa(job #335303)

Utilizator DraStiKDragos Oprica DraStiK Data 29 iulie 2009 14:51:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <string.h>

#define DIM 2000005
#define MAX 1005

char a[DIM],b[DIM];
int pi[DIM],poz[MAX];
int n,m,nrt;

void read ()
{
    gets (a+1);
    n=strlen (a+1);
    gets (b+1);
    m=strlen (b+1);
}

void kmp (char a[DIM])
{
    int i,k;

    for (k=0, i=2; i<=n; ++i)
    {
        for ( ; a[k+1]!=a[i] && k>0; )
            k=pi[k];
        if (a[k+1]==a[i])
            ++k;
        pi[i]=k;
    }
}

void solve ()
{
    int i,k;

    for (k=0, i=1; i<=m; ++i)
    {
        for ( ; a[k+1]!=b[i] && k>0; )
            k=pi[k];
        if (a[k+1]==b[i])
            ++k;
        if (k==n)
        {
            ++nrt;
            if (nrt<=1000)
                poz[nrt]=i-n;
            k=pi[k];
        }
    }

}

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

void print ()
{
    int i,t;

    printf ("%d\n",nrt);
    for (i=1, t=min (nrt,1000); i<=t; ++i)
        printf ("%d ",poz[i]);
}

int main ()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);

    read ();
    kmp (a);
    solve ();
    print ();

    return 0;
}