Pagini recente » Cod sursa (job #991387) | Cod sursa (job #313829) | Cod sursa (job #1948536) | Cod sursa (job #2100753) | Cod sursa (job #2801293)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Nmax 2000005
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 )
{
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" );
char text[ Nmax ] , word[ Nmax ];
int n , vect[ 1001 ]={0};
fscanf( in , "%s %s" , word , text );
n = KMP( word , text , vect );
fprintf( out , "%d\n" , n );
for( int i = 0 ; i < n ; i ++ )
fprintf( out , "%d " , vect[ i ]);
}