Pagini recente » Cod sursa (job #2795722) | Cod sursa (job #1872833) | Cod sursa (job #2863226) | Cod sursa (job #414141) | Cod sursa (job #2801304)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Nmax 2000005
char text[ Nmax ] , word[ Nmax ];
int prec[ Nmax ];
int min( int a , int b )
{
if( a < b )
return a ;
return b ;
}
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 < min(n , 1000) ; i ++ )
fprintf( out , "%d " , vect[ i ]);
}