Source code for submission s1020

bugs.cpp

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4.  
  5. int main() {
  6. 	int nrows;
  7. 	char key[2000];
  8. 	char line[2000002];
  9. 	int *begin = new int[2000002];
  10. 	int *end = new int[2000002];
  11. 	bool print[2000002];
  12. 	//gets (line);
  13. 	//printf ("%s", line);
  14. 	while (scanf ("%d %s", &nrows, key) == 2) {
  15. 		int ksize = strlen (key);
  16. 		char dummy[10];
  17. 		gets (dummy);
  18. 		for (int i = 0; i < nrows; i++) {
  19. 			gets (line);
  20. 			int size = strlen (line);
  21. 			if (size == 0) {
  22. 				printf ("\n");
  23. 				continue;
  24. 			}
  25.  
  26. 			//printf ("%s\n", line);
  27. 			int prev = 0;
  28. 			for (int j = 0; j < size; j++) {
  29. 				if (line[j] == key[prev]) {
  30. 					prev++;
  31. 					begin[j] = prev;
  32. 				} 
  33. 				else if (line[j] == key[0]) {
  34. 					begin[j] = 1;
  35. 					prev = 1;
  36. 				}
  37. 				else begin[j] = 0;
  38. 				prev = begin[j] % ksize;
  39. 			}
  40.  
  41. 			/*
  42. 			for (int j = 0; j < size; j++)
  43. 				printf ("%d ", begin[j]);
  44. 			printf ("\n");
  45. 			*/
  46.  
  47. 			prev = ksize - 1;
  48. 			for (int j = size - 1; j >= 0; j--) {
  49. 				if (line[j] == key[prev]) {
  50. 					end[j] = ksize - prev;
  51. 					prev--;
  52. 				}
  53. 				else if (line[j] == key[ksize - 1]) {
  54. 					end[j] = 1;
  55. 					prev = ksize - 2;
  56. 				}
  57. 				else end[j] = 0;
  58. 				if (prev < 0) prev += ksize;
  59. 			}
  60. 			/*
  61. 			for (int j = 0; j < size; j++)
  62. 				printf ("%d ", end[j]);
  63. 			printf ("\n");
  64. 			*/
  65. 			int pos = 0;
  66. 			memset (print, 1, sizeof (print));
  67. 			for ( ; ;) {
  68. 				if (begin[pos] == ksize)  {
  69. 					memset (print + pos - ksize + 1, 0, ksize);
  70.  
  71. 					int bpos = pos - ksize;
  72. 					int epos = pos + 1;
  73. 					//printf ("%d %d\n", bpos, epos);
  74.  
  75. 					while (bpos >= 0 && epos < size) {
  76. 						if (begin[bpos] + end[epos] == ksize && print[bpos] &&  print[epos]) {
  77. 							memset (print + (bpos - begin[bpos]) + 1, 0, begin[bpos]);
  78. 							memset (print + epos, 0, end[epos]);
  79. 							bpos = bpos - begin[bpos];
  80. 							epos = epos + end[epos];
  81. 						}
  82. 						else break;
  83. 					}
  84. 				}
  85. 				pos++;
  86. 				if (pos == size) break;
  87. 			}
  88. 			/*
  89. 			for (int i = 0; i < size; i++)
  90. 				printf ("%d ", print[i]);
  91. 			printf ("\n");
  92. 			*/
  93. 			for (int i = 0; i < size; i++)
  94. 				if (print[i])
  95. 					printf ("%c", line[i]);
  96. 			printf("\n");
  97. 		}
  98. 	}
  99.  
  100. 	return 0;
  101. }