Source code for submission s1024

bugs.cpp

  1. #include <stdio.h>
  2. #include <deque>
  3.  
  4. using namespace std;
  5.  
  6. deque< pair< char, int > > stack;
  7. char bugword[1001];
  8. int errors[1001];
  9. int END;
  10. char c;
  11.  
  12. void printline() {
  13. while( !stack.empty() ) {
  14. printf( "%c", stack.front().second );
  15. stack.pop_front();
  16. }
  17.  
  18. printf( "\n" );
  19. }
  20.  
  21. void readbug() {
  22. char c;
  23. END = 1;
  24. while( true ) {
  25. c = getchar();
  26. if( c == '\n' ) {
  27. break;
  28. }
  29.  
  30. bugword[END++] = c;
  31. }
  32.  
  33. // build error edges
  34. errors[0] = 0;
  35. errors[1] = 0;
  36. for( int i = 2; i < END; i++ ) {
  37. int last = errors[ i - 1 ];
  38. bool set = false;
  39.  
  40. while( last != 0 ) {
  41. if( bugword[ last + 1 ] == bugword[ i ] ) {
  42. errors[ i ] = last + 1;
  43. set = true;
  44. break;
  45. }
  46.  
  47. last = errors[ last ];
  48. }
  49.  
  50. if( !set ) {
  51. errors[ i ] = ( bugword[1] == bugword[i] ) ? 1 : 0;
  52. }
  53. }
  54. }
  55.  
  56.  
  57. void remove_bug() {
  58. for( int i = 2; i < END; i++ ) {
  59. stack.pop_back();
  60. }
  61. }
  62.  
  63. int getpos( int last, char c ) {
  64. while( last != 0 ) {
  65. if( bugword[ last + 1 ] == c ) {
  66. return last + 1;
  67. }
  68.  
  69. last = errors[ last ];
  70. }
  71.  
  72. return ( bugword[ 1 ] == c ) ? 1 : 0;
  73. }
  74.  
  75. pair< int, char > create( char c, int pos ){
  76. return pair<int,char>( pos, c );
  77. }
  78.  
  79.  
  80. int main() {
  81. int l, last;
  82. while( scanf( "%d ", &l ) == 1 ) {
  83. readbug();
  84.  
  85. for( int i = 0; i < l; i++ ) {
  86. stack.clear();
  87. last = 0;
  88.  
  89. while( true ) {
  90. c = getchar();
  91. if( c == '\n' ) {
  92. printline();
  93. break;
  94. }
  95.  
  96. last = getpos( last, c );
  97. if( last == ( END - 1 ) ) {
  98. remove_bug();
  99. last = stack.back().first;
  100. } else {
  101. stack.push_back( create( c, last ) );
  102. }
  103. }
  104. }
  105. }
  106.  
  107. return 0;
  108. }
  109.