Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef struct { const char *needle; size_t npos; size_t len; size_t *prefix_table; } kmp_ctx; void kmp_init(kmp_ctx *ctx, const char *needle) { 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) { int T; char B[1024]; char line[2000004]; char line2[2000004]; int Blen; while (scanf(" %d %s", &T, B) == 2) { Blen = strlen(B); while (getchar() != '\n'); kmp_ctx ctx; kmp_init(&ctx, B); for (int i = 0; i < T; i++) { ctx.npos = 0; fgets(line, 2000004, stdin); char *s = line; char *out = line2; while (*s != '\0') { *out = *s; if (kmp_step(&ctx, *s)) { out -= Blen; for (char *x = out - Blen; x <= out; x++) { kmp_step(&ctx, *x); } } out++; s++; } *out = '\0'; printf("%s", line2); } } return 0; }
--- 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); } }