Cod sursa(job #2801301)

Utilizator dragossofiaSofia Dragos dragossofia Data 15 noiembrie 2021 21:06:48
Problema Potrivirea sirurilor Scor 40
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define Nmax 2000005
char text[ Nmax ] , word[ Nmax ];
int prec[ Nmax ];

void genPrec(  )
{
    int n = strlen( word ) , i , j;


    j = 0 ;
    prec[ 0 ] =  0 ;

    for( i = 1 ; i < n ; i++ )
    {
        if( word[ i ] == word[ j ] )
        {
            j ++ ;
            prec[ i ] = j ;
        }
        else
        {
            if( j != 0 )
            {
                j = prec[ j - 1 ];
                i -- ;
            }
            else
            {
                j = 0 ;
                prec[ i ] = 0 ;
            }
        }
    }


}

int KMP(   int vect[] )
{

    int  i , j , n , m , nrFound = 0;

    genPrec(  );

    n = strlen( word );
    m = strlen( text );
    if( n > m )
        return 0 ;
    i = j = 0 ;
    while( i < m)
    {
        if( word[ j ] == text[ i ] )
        {
            i++;
            j++;
        }
        if( j == n )
        {
            if( nrFound < 1000)
                vect[ nrFound ] = i - j ;
            nrFound ++ ;
            j = prec[ j - 1 ];

        }
        if( word[ j ] != text[ i ] && i < m)
        {
            if( j != 0 )
            {
                j = prec[ j - 1 ];
            }
            else
                {
                        i++ ;
                }
        }


    }
    return nrFound ;
}

int main()
{   FILE *in , *out;
    in = fopen("strmatch.in", "r" );
    out = fopen("strmatch.out" , "w" );

    int n , vect[ 1024 ]={0};
    fscanf( in , "%s %s" , word , text );
    n = KMP(  vect );
    fprintf( out , "%d\n" , n );
    for( int i = 0 ; i < n ; i ++ )
        fprintf( out , "%d " , vect[ i ]);
}