Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.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 *l1 = line; char *l2 = line2; char *tmp; char *s = l1; char *out = l2; bool changed; do { changed = false; while (*s != '\0') { *out = *s; if (kmp_step(&ctx, *s)) { out -= Blen; changed = true; } out++; s++; } *out = '\0'; tmp = l1; l1 = l2; l2 = tmp; s = l1; out = l2; } while (changed); printf("%s", line); } } return 0; }
--- 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;