Source code for submission s840

Go to diff to previous submission

bugs.cpp

  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <assert.h>
  6.  
  7. typedef struct {
  8. const char *needle;
  9. size_t npos;
  10. size_t len;
  11. size_t *prefix_table;
  12. } kmp_ctx;
  13.  
  14. void kmp_init(kmp_ctx *ctx, const char *needle) {
  15. size_t nlen = strlen(needle);
  16. ctx->len = nlen;
  17. ctx->needle = needle;
  18. ctx->npos = 0;
  19. ctx->prefix_table = (size_t *)malloc(sizeof(size_t) * (nlen + 1));
  20.  
  21. size_t i = 0;
  22. ssize_t j = -1;
  23.  
  24. ctx->prefix_table[i] = j;
  25. while (i < nlen) {
  26. while (j >= 0 && needle[i] != needle[j]) {
  27. j = ctx->prefix_table[j];
  28. }
  29. i++; j++;
  30. ctx->prefix_table[i] = j;
  31. }
  32. }
  33.  
  34. bool kmp_step(kmp_ctx *ctx, char ch) {
  35. while (ctx->npos != 0 && ch != ctx->needle[ctx->npos]) {
  36. ctx->npos = ctx->prefix_table[ctx->npos];
  37. }
  38.  
  39. if (ch == ctx->needle[ctx->npos]) {
  40. ctx->npos++;
  41.  
  42. if (ctx->npos == ctx->len) {
  43. ctx->npos = 0;
  44. return true;
  45. }
  46. }
  47.  
  48. return false;
  49. }
  50.  
  51. int main(void) {
  52. int T;
  53. char B[1024];
  54. char line[2000004];
  55.  
  56. char line2[2000004];
  57.  
  58. int Blen;
  59.  
  60. while (scanf(" %d %s", &T, B) == 2) {
  61. Blen = strlen(B);
  62.  
  63. while (getchar() != '\n');
  64.  
  65. kmp_ctx ctx;
  66. kmp_init(&ctx, B);
  67.  
  68. for (int i = 0; i < T; i++) {
  69. ctx.npos = 0;
  70.  
  71. fgets(line, 2000004, stdin);
  72.  
  73. char *s = line;
  74. char *out = line2;
  75. while (*s != '\0') {
  76. *out = *s;
  77. if (kmp_step(&ctx, *s)) {
  78. out -= Blen;
  79. for (char *x = out - Blen; x <= out; x++) {
  80. kmp_step(&ctx, *x);
  81. }
  82.  
  83. }
  84. out++; s++;
  85. }
  86. *out = '\0';
  87.  
  88. printf("%s", line2);
  89. }
  90. }
  91.  
  92. return 0;
  93. }
  94.  

Diff to submission s802

bugs.cpp

--- c4.s802.cteam091.bugs.cpp.0.bugs.cpp
+++ c4.s840.cteam091.bugs.cpp.0.bugs.cpp
@@ -3,5 +3,5 @@
 #include <stdlib.h>
 #include <string.h>
-
+#include <assert.h>
 
 typedef struct {
@@ -71,19 +71,14 @@
                         fgets(line, 2000004, stdin);
                 
-                        char *l1 = line;
-                        char *l2 = line2;
-                        char *tmp;
-                        
-                        char *s = l1;
-                        char *out = l2;
-                        bool changed;
-                        do {
-                                changed = false;
-                                
+                        char *s = line;
+                        char *out = line2;
                                 while (*s != '\0') {
                                         *out = *s;
                                         if (kmp_step(&ctx, *s)) {
                                                 out -= Blen;
-                                                changed = true;
+                                                for (char *x = out - Blen; x <= out; x++) {
+                                                        kmp_step(&ctx, *x);
+                                                }
+                        
                                         }
                                         out++; s++;
@@ -91,13 +86,5 @@
                                 *out = '\0';
                                 
-                                tmp = l1;
-                                l1 = l2;
-                                l2 = tmp;
-                                
-                                s = l1;
-                                out = l2;
-                        } while (changed);
-                        
-                        printf("%s", line);
+                        printf("%s", line2);
                 }
         }