Cod sursa(job #2801287)

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

#define Nmax 100000

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 )
        {
            vect[ nrFound ] = i - j ;
            nrFound ++ ;
            j = prec[ j - 1 ];
        }
        if( word[ j ] != text[ i ] )
        {
            if( j != 0 )
            {
                j = prec[ j - 1 ];
            }
            else
                {   
                        i++ ;
                }
        }


    }
    return nrFound ;
}

int main()
{
    char text[ Nmax ] , word[ Nmax ];
    int n , vect[ Nmax ]={0};
    scanf( "%s %s" , word , text );
    n = KMP( word , text , vect );
    printf( "%d\n" , n );
    for( int i = 0 ; i < n ; i ++ )
        printf( "%d " , vect[ i ]);
}