Cod sursa(job #159783)

Utilizator sealTudose Vlad seal Data 14 martie 2008 13:27:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<string.h>
#define Nm (1<<21)
#define Km 1000
char A[Nm],B[Nm];
int Pi[Nm],Ans[Km+1],ans,k;

void read()
{
    freopen("strmatch.in","r",stdin);
    gets(A+1);
    gets(B);
}

void solve()
{
    int i,p,n=strlen(A+1);

    Pi[1]=p=0;
    for(i=2;i<=n;++i)
    {
        while(p && A[p+1]!=A[i])
            p=Pi[p];
        if(A[p+1]==A[i])
            ++p;
        Pi[i]=p;
    }

    for(p=i=0;B[i];++i)
    {
        while(p && A[p+1]!=B[i])
            p=Pi[p];
        if(A[p+1]==B[i])
            ++p;
        if(p==n)
        {
            ++ans;
            p=Pi[p];
            if(k<Km)
                Ans[++k]=i-n+1;
        }
    }
}

void write()
{
    int i;

    freopen("strmatch.out","w",stdout);
    printf("%d\n",ans);
    if(!k)
        return;
    for(i=1;i<k;++i)
        printf("%d ",Ans[i]);
    printf("%d\n",Ans[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}