Cod sursa(job #1148122)

Utilizator octavdOctavian Dumitrascu octavd Data 20 martie 2014 14:36:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstring>
#include <cstdio>
using namespace std;
int i,K,N,M,nr;
char X[1000005],Y[1000005];
int Pi[1000005],d[1000005];


void constructie_pi() //constructia pi-ului
{
        N=strlen(X)-1;
        K=0;
        Pi[1]=0; // trebuie  Pi[i]<i deci  Pi[1]=0
        for (i=2;i<=N;i++)
        {
                while (K>0&&X[i]!=X[K+1])//cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
                        K=Pi[K];
                if (X[i]==X[K+1]) K=K+1;  // daca literele coicid cresc K
                Pi[i]=K;
        }
}

int main()
{
        freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);
        gets(X+1);
        gets(Y+1);
        X[0]=' ';
        Y[0]=' ';
        M=strlen(Y)-1;
        constructie_pi();
        K=0;
        for (i=1; i<=M; i++)
        {
                while (K>0&&Y[i]!=X[K+1])//cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
                    K=Pi[K];
                if (Y[i]==X[K+1]) K=K+1;  // daca literele coincid creste K
                d[i]=K;
        }
        nr=0;
        for (i=1;i<=M;i++)
            if (d[i]==N) nr++;
        printf("%d\n",nr);
        for (i=1;i<=M;i++)
            if (d[i]==N) printf("%d ",i-N);
        return 0;
}