Cod sursa(job #1148147)

Utilizator octavdOctavian Dumitrascu octavd Data 20 martie 2014 15:22:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstring>
#include <cstdio>
using namespace std;
int i,K,N,M,nr,c;
char X[2000005],Y[2000005];
int Pi[2000005],d[2000005];


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);
        c=0;
        for (i=1;i<=M;i++)
            if (d[i]==N)
            {
                printf("%d ",i-N);
                c++;
                if (c==1000) break;
            }
        return 0;
}