Cod sursa(job #870601)

Utilizator Athena99Anghel Anca Athena99 Data 3 februarie 2013 18:11:04
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cassert>
#include <cstdio>
#include <cstring>

const int d1=2000002,d2=1002;
int p[d1],s[d2];
char c[d1],v[d1];

int main()
{
    int sol=0,i=1,k=0,n=0,m=0;

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

    gets(c+1);
    gets(v+1);
    n=strlen(c+1);
    m=strlen(v+1);

    for (i=1; i<=m; ++i)
    {
        while (k>0 && v[i]!=c[k+1])
            k=p[k];

        if (v[i]==c[k+1])
            ++k;

        p[i]=k;

        if (p[i]==n)
            s[++sol]=i-n;
    }

    if (sol>1000)
        sol=1000;
    assert(printf("%d\n",sol));
    for (i=1; i<=sol; ++i)
        assert(printf("%d ",s[i]));

    return 0;
}