bugs.cpp

#include <stdio.h>
#include <deque>
 
using namespace std;
 
deque< pair< char, int > > stack;
char bugword[1001];
int errors[1001];
int END;
char c;
 
void printline() {
	while( !stack.empty() ) {
		printf( "%c", stack.front().second );
		stack.pop_front();
	}
 
	printf( "\n" );
}
 
void readbug() {
	char c;
	END = 1;
	while( true ) {
		c = getchar();
		if( c == '\n' ) {
			break;
		}
 
		bugword[END++] = c; 
	}
 
	// build error edges
	errors[0] = 0;
	errors[1] = 0;
	for( int i = 2; i < END; i++ ) {
		int last = errors[ i - 1 ];
		bool set = false;
 
		while( last != 0 ) {
			if( bugword[ last + 1 ] == bugword[ i ] ) {
				errors[ i ] = last + 1;
				set = true;
				break;
			}
 
			last = errors[ last ];
		}
 
		if( !set ) {
			errors[ i ] = ( bugword[1] == bugword[i] ) ? 1 : 0; 
		}
	}
}
 
 
void remove_bug() {
	for( int i = 2; i < END; i++ ) {
		stack.pop_back();
	}
}
 
int getpos( int last, char c ) {
	while( last != 0 ) {
		if( bugword[ last + 1 ] == c ) {
			return last + 1;
		}
 
		last = errors[ last ];
	}
 
	return ( bugword[ 1 ] == c ) ? 1 : 0;
}
 
pair< int, char > create( char c, int pos ){
	return pair<int,char>( pos, c );
}
 
 
int main() {
	int l, last;
	while( scanf( "%d ", &l ) == 1 ) {
		readbug();
 
		for( int i = 0; i < l; i++ ) {
			stack.clear();
			last = 0;
 
			while( true ) {
				c = getchar();
				if( c == '\n' ) {
					printline();
					break;
				}
 
				last = getpos( last, c );
				if( last == ( END - 1 ) ) {
					remove_bug();
					last = stack.back().first;
				} else {
					stack.push_back( create( c, last ) );
				}			
			}
		}
	}
 
	return 0;
}