Cod sursa(job #2801293)

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

#define Nmax 2000005

void genPrec( char word[] , int prec[] )
{
    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( char word[] , char text[] , int vect[] )
{   
    int prec[ Nmax ], i , j , n , m , nrFound = 0;
    
    genPrec( word , prec );

    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" );
    char text[ Nmax ] , word[ Nmax ];
    int n , vect[ 1001 ]={0};
    fscanf( in , "%s %s" , word , text );
    n = KMP( word , text , vect );
    fprintf( out , "%d\n" , n );
    for( int i = 0 ; i < n ; i ++ )
        fprintf( out , "%d " , vect[ i ]);
}