Source code for submission s1131

Go to diff to previous submission

bugs.cpp

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

Diff to submission s1089

bugs.cpp

--- c4.s1089.cteam008.bugs.cpp.0.bugs.cpp
+++ c4.s1131.cteam008.bugs.cpp.0.bugs.cpp
@@ -5,10 +5,11 @@
 
 deque< pair< int, char > > stack;
-char bugword[1001];
-int errors[1001];
+char bugword[10000];
+int errors[10000];
 int END;
 char c;
 
 void printline() {
+        stack.pop_front();
         while( !stack.empty() ) {
                 printf( "%c", stack.front().second );
@@ -85,5 +86,7 @@
                 for( int i = 0; i < l; i++ ) {
                         stack.clear();
+                        stack.push_back( create( '#', 0 ) );
                         last = 0;
+        
 
                         while( true ) {