Pagini recente » Profil NotTheRealGeorge | Cod sursa (job #135344) | Monitorul de evaluare | Profil Ignus | Cod sursa (job #152076)
Cod sursa(job #152076)
#include <stdio.h>
#include <string.h>
#define NX 2000010
char P[ NX ], T[ NX ];
int M, N, pi[ NX ], sol[ 1024 ];
void cit() {
gets( P + 1 ); M = strlen( P + 1 ); // the pattern
gets( T + 1 ); N = strlen( T + 1 ); // the text
P[0] = T[0] = 0;
}
void calc_pi() {
int i, k;
for( k = pi[0] = -1, i = 1; i <= M; pi[ i++ ] = ++k )
while( P[ i ] != P[ k+1 ] && k != -1 )
k = pi[k];
}
void rez() {
int i, k;
calc_pi();
for( k = 0, i = 1; i <= N; i++ ) {
while( T[i] != P[ k+1 ] && k != -1 )
k = pi[k];
if( ++k == M )
sol[ ++sol[0] ] = i - M;
}
}
void scr() {
int i, min = 1000 < sol[0] ? 1000 : sol[0];
printf( "%d\n", sol[0] );
for( i = 1; i <= min; i++ )
printf( "%d ", sol[i] );
}
int main() {
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
cit();
rez();
scr();
return 0;
}