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;