Cod sursa(job #938809)

Utilizator Athena99Anghel Anca Athena99 Data 13 aprilie 2013 22:54:00
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cassert>
#include <cstdio>
#include <cstring>

const int nmax=2000010;
int p[nmax],sol[1010];
int n=0,m=0,i=0,k=0,s=0;
char a[nmax],b[nmax];

void prefix()
{
    p[1]=0;
    for (i=2; i<n+1; ++i)
    {
        while (k>0 && a[k+1]!=a[i])
            k=p[k];

        if (a[k+1]==a[i])
            ++k;

        p[i]=k;
    }
}

void x()
{
    for (i=1; i<m+1; ++i)
    {
        while (k>0 && a[k+1]!=b[i])
            k=p[k];

        if (a[k+1]==b[i])
            ++k;

        if (n==k)
        {
            sol[++s]=i-n;
            if (s>1000)
            {
                s=1000;
                i=m+1;
            }
        }

    }

}

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

    assert(scanf("%s%s",a+1,b+1));

    n=strlen(a+1);
    m=strlen(b+1);

    prefix();
    x();

    if (s>1000)
        assert(printf("1000\n"));
    else
        assert(printf("%d\n",s));

    for (i=1; i<s+1; ++i)
        assert(printf("%d ",sol[i]));

    assert(printf("\n"));

    return 0;
}