Pagini recente » Rating Ficuta David (disappointment) | Cod sursa (job #1943376) | Statistici Hij Lucian (Gainusa) | Cod sursa (job #1007553) | Cod sursa (job #1567460)
#include <cstdio>
#include <cstring>
const int DIM = 1 << 21;
using namespace std;
int Answer[DIM], cnt_answer;
int Prefix[DIM], N, M, length;
char Pattern[DIM], String[DIM];
int main () {
freopen( "strmatch.in" , "r", stdin );
freopen( "strmatch.out", "w", stdout );
scanf( "%s", Pattern + 1 ); N = strlen( Pattern + 1 );
scanf( "%s", String + 1 ); M = strlen( String + 1 );
length = 0;
for( int i = 2; i <= N; i ++ ) {
while( length && Pattern[i] != Pattern[length + 1] )
length = Prefix[length];
if( Pattern[i] == Pattern[length + 1] )
length ++;
Prefix[i] = length;
}
length = 0;
for( int i = 1; i <= M; i ++ ) {
while( length && String[i] != Pattern[length + 1] )
length = Prefix[length];
if( String[i] == Pattern[length + 1] )
length ++;
if( length == N ) {
if( cnt_answer < 1000 )
Answer[++cnt_answer] = i - length;
length = Prefix[length];
}
}
printf( "%d\n", cnt_answer );
for( int i = 1; i <= cnt_answer; i ++ )
printf( "%d ", Answer[i] );
return 0;
}