Cod sursa(job #651852)

Utilizator rootsroots1 roots Data 21 decembrie 2011 20:33:18
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <cstring>

#define PL 2000002
#define TL 2000002

#define vL 1001

int L[PL];
int v[vL];

char P[PL];
char T[TL];

int main()
{
    int M,N;

    freopen("strmatch.in","r",stdin);

    fgets(P+1,PL,stdin);
    fgets(T+1,TL,stdin);

    M=strlen(P+1)-1;
    N=strlen(T+1)-1;

    for(int k=0,i=2;i<=M;++i)
    {
        for(;k&&P[i]==P[k+1];k=L[k]);
        if(P[k+1]==P[i]) ++k;
        L[i]=k;
    }

    for(int k=0,i=1;i<=N;++i)
    {
        for(;k&&P[k+1]!=T[i];k=L[k]);
        if(P[k+1]==T[i]) ++k;
        if(k==M)
        {
            ++v[0];
            if(v[0]<=1000) v[v[0]]=i-M;
        }
    }

    freopen("strmatch.out","w",stdout);

    printf("%d\n",v[0]);
    for(int i=1;i<v[0]&&i<1000;++i)
        printf("%d ",v[i]);
    if(v[0]<1000) printf("%d\n",v[v[0]]);
    else printf("%d\n",v[1000]);

    return 0;
}