Cod sursa(job #481968)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 2 septembrie 2010 10:14:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<algorithm>
using namespace std;

#define DIM 2000005
#define DIM2 1005

char a[DIM],b[DIM];
int n,m,prefix[DIM],sol[DIM2],vf;

void kmp ()
{
    int i,q;

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

    for(q=0,i=1;i<=m;++i)
    {
        while(q>0 && a[q+1]!=b[i])
            q=prefix[q];
        if(a[q+1]==b[i])
            ++q;
        if(q==n)
        {
            ++vf;
            sol[min(vf,1001)]=i-n;
            q=prefix[q];
        }
    }
}

void show ()
{
    int i,vf2=min(vf,1000);

    printf("%d\n",vf);
    for(i=1;i<=vf2;++i)
        printf("%d ",sol[i]);
}

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

    gets (1+a);
    n=strlen(1+a);
    gets (1+b);
    m=strlen(1+b);
    kmp ();
    show ();
    return 0;
}