Cod sursa(job #525591)

Utilizator DraStiKDragos Oprica DraStiK Data 25 ianuarie 2011 16:23:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define DIM 2000005

char a[DIM],b[DIM];
vector <int> v;
int pi[DIM];
int n,m,nrt;

void read ()
{
    fgets (a+1,DIM,stdin);
    n=strlen (a+1)-(a[strlen (a+1)]=='\n');
    fgets (b+1,DIM,stdin);
    m=strlen (b+1)-(b[strlen (b+1)]=='\n');
}

void solve ()
{
    int i,k;

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

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

void print ()
{
    vector <int> :: iterator it;

    printf ("%d\n",nrt);
    for (it=v.begin ();it!=v.end (); ++it)
        printf ("%d ",*it);
}

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

    read ();
    solve ();
    print ();

    return 0;
}