Cod sursa(job #411846)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 5 martie 2010 10:35:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <string.h>

#define num (nr++)>=999?1000:nr
#define size 2000003

using namespace std;

char S1[size],S2[size];
int *poz;
int rez[1005];
int nr,lg1,lg2;

void citire()
{
    fgets(S1+1,size,stdin);
    S1[strlen(S1+1)]=0;
    fgets(S2+1,size,stdin);
    S2[strlen(S2+1)]=0;
    poz = new int[lg1];
    lg1=strlen(S1+1);
    lg2=strlen(S2+1);
}

void prefix()
{
    int k=0;
    poz[0]=poz[1]=0;
    for (int i=2;i<=lg1;i++)
    {
        while (k!=0 && S1[i]!=S1[k+1])
            k=poz[k];
        if (S1[i]==S1[k+1])
            k++;
        poz[i]=k;
    }
}

void solve()
{
    int k=0;
    for (int j=1;j<=lg2;j++)
    {
        while (k!=0 && S2[j]!=S1[k+1])
            k=poz[k];
        if (S2[j]==S1[k+1])
            k++;
        if (k==lg1)
        {
            if (nr<1000)
                rez[nr]=j;
            nr++;
            k=poz[k];
        }
    }
    printf("%d\n",nr);
    for (int i=0;i<nr;i++)
        printf("%d ",rez[i]-lg1);
}

int main ()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    citire();
    prefix();
    solve();
    return 0;
}