Cod sursa(job #1585273)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 30 ianuarie 2016 21:41:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <string.h>
#include <stdio.h>

#define MAXN 2000005

char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN],r[1005];
int i, K, N, M, ct;

void constructie_pi() //constructia pi-ului
{
        N = strlen(X)-1;
        K = 0;     // iteratorul K care ne ajuta la contructia lui Pi
        Pi[1] = 0; // Pi[i] < i => 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
                        K = Pi[K];                                      // nu coincid sar din K in Pi[K]
                if (X[i] == X[K+1]) K = K + 1;  // daca literele coicid
                Pi[i] = K;
        }
}

int main()
{
        freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);

        fgets(X+1, MAXN, stdin);
        fgets(Y+1, MAXN, stdin);
        X[0] = ' '; Y[0] = ' ';
        X[strlen(X)-1] = Y[strlen(Y)-1] = 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
                        K = Pi[K];                                      // nu coincid sar din K in Pi[K]
                if (Y[i] == X[K+1]) K = K + 1;  // daca literele coincid
                d[i] = K;
                if(d[i]==N){ct++;
                if(ct<=1000)
                r[ct]=i-N;
                }
        }
       printf("%d\n",ct);
       if(ct<=1000)
        for (i = 1;  i <=ct; ++i)
            printf("%d ",r[i]);
            else for (i = 1;  i <=1000; ++i)
            printf("%d ",r[i]);
}