Source code for submission s802

Go to diff to previous submission

bugs.cpp

  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  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 *l1 = line;
  74. char *l2 = line2;
  75. char *tmp;
  76.  
  77. char *s = l1;
  78. char *out = l2;
  79. bool changed;
  80. do {
  81. changed = false;
  82.  
  83. while (*s != '\0') {
  84. *out = *s;
  85. if (kmp_step(&ctx, *s)) {
  86. out -= Blen;
  87. changed = true;
  88. }
  89. out++; s++;
  90. }
  91. *out = '\0';
  92.  
  93. tmp = l1;
  94. l1 = l2;
  95. l2 = tmp;
  96.  
  97. s = l1;
  98. out = l2;
  99. } while (changed);
  100.  
  101. printf("%s", line);
  102. }
  103. }
  104.  
  105. return 0;
  106. }
  107.  

Diff to submission s788

bugs.cpp

--- c4.s788.cteam091.bugs.cpp.0.bugs.cpp
+++ c4.s802.cteam091.bugs.cpp.0.bugs.cpp
@@ -4,5 +4,5 @@
 #include <string.h>
 
-/*
+
 typedef struct {
         const char *needle;
@@ -13,7 +13,39 @@
 
 void kmp_init(kmp_ctx *ctx, const char *needle) {
-        size
+        size_t nlen = strlen(needle);
+        ctx->len = nlen;
+        ctx->needle = needle;
+        ctx->npos = 0;
+        ctx->prefix_table = (size_t *)malloc(sizeof(size_t) * (nlen + 1));
+        
+        size_t i = 0;
+        ssize_t j = -1;
+        
+        ctx->prefix_table[i] = j;
+        while (i < nlen) {
+                while (j >= 0 && needle[i] != needle[j]) {
+                        j = ctx->prefix_table[j];
+                }
+                i++; j++;
+                ctx->prefix_table[i] = j;
+        }
+}
+
+bool kmp_step(kmp_ctx *ctx, char ch) {
+        while (ctx->npos != 0 && ch != ctx->needle[ctx->npos]) {
+                ctx->npos = ctx->prefix_table[ctx->npos];
+        }
+        
+        if (ch == ctx->needle[ctx->npos]) {
+                ctx->npos++;
+                
+                if (ctx->npos == ctx->len) {
+                        ctx->npos = 0;
+                        return true;
+                }
+        }
+
+        return false;
 }
-*/
 
 int main(void) {
@@ -31,5 +63,10 @@
                 while (getchar() != '\n');
                 
+                kmp_ctx ctx;
+                kmp_init(&ctx, B);
+                
                 for (int i = 0; i < T; i++) {
+                        ctx.npos = 0;
+                
                         fgets(line, 2000004, stdin);
                 
@@ -42,14 +79,15 @@
                         bool changed;
                         do {
-                                char *f;
                                 changed = false;
-                                while ((f = strstr(s, B)) != NULL) {
-                                        changed = true;
-                                        while (s != f) {
-                                                *(out++) = *(s++);
+                                
+                                while (*s != '\0') {
+                                        *out = *s;
+                                        if (kmp_step(&ctx, *s)) {
+                                                out -= Blen;
+                                                changed = true;
                                         }
-                                        s += Blen;
+                                        out++; s++;
                                 }
-                                strcpy(out, s); 
+                                *out = '\0';
                                 
                                 tmp = l1;