Pagini recente » Cod sursa (job #2901698) | Cod sursa (job #320401) | Cod sursa (job #1979760) | Cod sursa (job #2132972) | Cod sursa (job #2801301)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Nmax 2000005
char text[ Nmax ] , word[ Nmax ];
int prec[ Nmax ];
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 < n ; i ++ )
fprintf( out , "%d " , vect[ i ]);
}