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. }