Pagini recente » Cod sursa (job #1457890) | Cod sursa (job #912843) | Cod sursa (job #2064044) | Cod sursa (job #1837914) | Cod sursa (job #2801289)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Nmax 100000
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 )
{
vect[ nrFound ] = i - j ;
nrFound ++ ;
j = prec[ j - 1 ];
}
if( word[ j ] != text[ i ] )
{
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[ Nmax ]={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 ]);
}