Cod sursa(job #2801542)

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


#define Nmax 2000005
#define d 256
#define q 49157
char text[ Nmax ] , word[ Nmax ];
int prec[ Nmax ];

int min( int a  , int b )
{
    if( a < b )
        return a ;
    return b ;
}

int RabinKarp( int vect[ ] )
{
    int p = 1 , hText = 0 , hWord = 0 , i , j , nrFound = 0 , match ;
    int n = strlen( word );
    int m = strlen( text );

    if( n > m )
        return 0 ;
    
    for( i = 1 ; i <=  n - 1 ; i++ )
        p = (p * d) % q;
    
    for( i = 0 ; i < n ; i ++ )
    {
        hWord = ( d * hWord + word[ i ] ) % q ;
        hText = ( d * hText + text[ i ] ) % q ;
    }
    
    for( i = 0 ; i <= m - n ; i++  )
    {  
        
        if( hText == hWord )
        {   
            match = 1 ;
            for( j = 0 ; j < n ; j ++ )
                if( word[ j ] != text[ j + i])
                    {
                        match = 0 ;
                        break ;
                    }
            if( match == 1 )
            {   
                if( nrFound < 1000 )
                    {
                        vect[ nrFound ] = i ;
                    }
                nrFound ++;
            }
        }
        
        if( i < m - n )
        {
            hText = ( ( hText - p * text[ i ] ) * d + text[ i + n ] ) % q ;
            if( hText < 0 )
                hText = hText + q ;
        }
    }
    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 = RabinKarp(  vect );
    fprintf( out , "%d\n" , n );
    for( int i = 0 ; i < min(n , 1000) ; i ++ )
        fprintf( out , "%d " , vect[ i ]);
}