Source code for submission s748

bugs.c

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. #define MAX_BUG_LEN 100
  6. #define MAX_LINE_LEN 2000000
  7.  
  8. /*
  9. #define DEBUG_PRINT(x, ...) fprintf(stderr, x, __VA_ARGS__)
  10. */
  11.  
  12. int main(void)
  13. {
  14. 	int line_count, i, bug_len;
  15. 	char bug[MAX_BUG_LEN+5], bug_reversed[MAX_BUG_LEN+5], bug_letters[27]; /*A-Z*/
  16. 	char *line = (char*)malloc(MAX_LINE_LEN+5);
  17. 	char *stack = (char*)malloc(MAX_LINE_LEN+5);
  18. 	int stack_len;
  19. 	char *line_ptr, *p;
  20. 	char *maybe_bug_chunk, *bug_on_stack;
  21.  
  22. 	while (scanf("%d %s ", &line_count, bug) == 2) {
  23. 		bug_len = strlen(bug);
  24. 		/* conpute bug reverse */
  25. 		for (i = 0; i < bug_len; ++i) {
  26. 			bug_reversed[bug_len-i-1] = bug[i];
  27. 		}
  28. 		bug_reversed[bug_len] = '\0';
  29.  
  30. 		/* compute bug letters */
  31. 		for (i = 0; i < 26; ++i) bug_letters[i] = '\0';
  32. 		for (i = 0; i < bug_len; ++i) {
  33. 			bug_letters[ bug[i] - 'A' ] = 1;
  34. 		}
  35.  
  36. /*		DEBUG_PRINT("bug is %s, reverse bug is %s, bug len is %d\n", bug, bug_reversed, bug_len);*/
  37.  
  38. 		/* process lines */		
  39. 		for (i = 0; i < line_count; ++i) {
  40. 			fgets(line, MAX_LINE_LEN+5, stdin);
  41. /*			DEBUG_PRINT("processing line %s", line);*/
  42. 			line_ptr = line;
  43. 			while ( (maybe_bug_chunk = strchr(line_ptr, bug[0])) ) {
  44. 				/* print until potential bug chunk */
  45. 				maybe_bug_chunk[0] = '\0';
  46. /*				DEBUG_PRINT("found potential chunk at line[%d]\n", maybe_bug_chunk - line);*/
  47. 				printf("%s", line_ptr);
  48. 				maybe_bug_chunk[0] = bug[0];
  49.  
  50. 				/* handle bug chunk */
  51. 				p = maybe_bug_chunk;
  52. 				stack_len = 0;
  53. 				while (*p >= 'A' && *p <= 'Z' && bug_letters[*p - 'A']) {
  54. 					stack[ stack_len++ ] = *p;
  55. 					p++;
  56. 					/* lze srovnat bug? */
  57. 					if (stack_len >= bug_len) {
  58. 						bug_on_stack = stack+stack_len-bug_len;
  59. 						if (strncmp(bug, bug_on_stack, bug_len) == 0) {
  60. 							/* srovnej bug */
  61. 							stack_len -= bug_len;
  62. 						}
  63. 					}
  64. 				}
  65. 				/* vypis toho, co zbyva na zasobniku */
  66. 				while (stack_len > 0) {
  67. 					fputc( stack[--stack_len], stdout );
  68. 				}
  69. 				/* END handle bug chunk */
  70. 				line_ptr = p;
  71. 			}
  72. 			/* vypis za poslednim bugem */
  73. 			printf("%s", line_ptr);
  74.  
  75. 		}
  76. 	}
  77.  
  78. 	free(line);
  79. 	free(stack);
  80. 	return 0;
  81. }
  82.  
  83.