Go to diff to previous submission
#include <stdio.h> #include <deque> using namespace std; deque< pair< int, char > > 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; }