Cod sursa(job #481966)

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

#define DIM 2000005
#define DIM2 1005

char a[DIM],b[DIM];
int n,m,s[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=s[q];
        if(a[q+1]==a[i])
            ++q;
        s[i]=q;
    }

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

void show ()
{
    int i;

    printf("%d\n",vf);
    for(i=1;i<=vf;++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;
}