Cod sursa(job #1747712)

Utilizator florinpocolPocol Florin florinpocol Data 25 august 2016 14:32:53
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.1 kb
//Knuth-Morris-Pratt

#include <stdio.h>

#define NMax 2000005

int m,n;
char M[NMax], N[NMax];    //Cei doi vectori
int pi[NMax];     //vectorul de prefixe
int pos[1024],p;   //vectorul de pozitii


void creare_prefix()
{
    int k=0;
    int i;

    pi[1]=0;
    for (i=2;i<=n; i++)
    {
        while (k>0 && N[k+1]!=N[i])
            k=pi[k];

        if (N[k+1]==N[i])
           k++;

        pi[i]=k;

    }
}

void  potrivire()
{
    int q=0;
    int i;

    for (i=0; i<=m; i++)
    {
        while (q>0 && N[q+1]!=M[i])
            q=pi[q];

        if (N[q+1]==M[i])
            q++;

        if (q==n)
        {
            p++;
            if (p<=1000)
                pos[p]=i-n;
        }

    }
}


int min(int p, int mmm)
{
    if (p<=mmm)
       return(p);
       else
       return(mmm);
}

void afisare()
{
    printf("%d\n",p);
    int i;
    for (i= 1; i<=min(p,1000); i++)
       printf("%d ",pos[i]);
}

int main(void)
{
   int i;

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

    fgets(N, sizeof(N), stdin);
    fgets(M, sizeof(M), stdin);

    /*
       TEORIE: prototype
       char *fgets(char *str, int n, FILE *stream) ;

       n -- This is the maximum number of characters to be read
           (including the final null-character).
           Usually, the length of the array passed as str is used.
    */

    for (; (N[n] >= 'A' && N[n] <= 'Z') || (N[n] >= 'a' && N[n] <= 'z')
            || (N[n] >= '0' && N[n] <= '9'); ++n);

    for (; (M[m] >= 'A' && M[m] <= 'Z') || (M[m] >= 'a' && M[m] <= 'z')
            || (M[m] >= '0' && M[m] <= '9'); ++m);




    for (i = n; i; --i)
                  N[i] = N[i-1];
    N[0] = ' ';

    for (i = m; i; --i)
                  M[i] = M[i-1];
    M[0] = ' ';


    //KMP: creare prefix
    p=0;
    creare_prefix();
    /*AFISARE PREFIX
        for (i=1; i<=n; i++)
                printf("%d ",pi[i]);
            printf("\n");
    */


    //KMP: ptrivire
    potrivire();

    afisare();


    return 0;
}