Pagini recente » Cod sursa (job #2325440) | Cod sursa (job #942389) | Cod sursa (job #174772) | Cod sursa (job #2614882) | Cod sursa (job #2801540)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Nmax 2000005
#define d 256
#define q 786433
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 ]);
}