Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 3000000 #define MAXM 4000 #define MOD 10000 char Line[MAXN]; int Hop[MAXN]; char Bug[MAXM]; int Pi[MAXM]; int Pos[MOD]; int nPos; void Compute(int m) { Pi[1] = 0; int k = 0; for(int q = 2; q <= m; q++) { while((k > 0) && (Bug[k + 1] != Bug[q])) { k = Pi[k]; } if(Bug[k + 1] == Bug[q]) { k++; } Pi[q] = k; } } void Next(int& i, int n) { i++; while((i <= n) && (Hop[i])) { i = Hop[i]; } Pos[nPos++ % MOD] = i; } void FindHops(int n, int m) { int q = 0; int i = 0; for(Next(i, n); i <= n; Next(i, n)) { while((q > 0) && (Bug[q + 1] != Line[i])) { q = Pi[q]; } if(Bug[q + 1] == Line[i]) { q++; } if(q == m) { Hop[Pos[(nPos - m) % MOD]] = i + 1; if(nPos < (m * 2) + 3) { nPos = 0; i = 0; q = 0; } else { nPos -= (m * 2) + 1; i = Pos[(nPos - 1) % MOD]; q = 0; } } } } int main() { int t; while(scanf("%d%s", &t, Bug + 1) > 0) { int m = strlen(Bug + 1); for(int i = 0; i <= m; i++) { Pi[i] = 0; } Compute(m); getchar(); for(int j = 0; j < t; j++) { nPos = 0; fgets(Line + 1, MAXN, stdin); int n = strlen(Line + 1); for(int i = 0; i <= n; i++) { Hop[i] = 0; } FindHops(n, m); int k = 0; for(Next(k, n); k <= n; Next(k, n)) { putchar(Line[k]); } } } /*for(int i = 0; i < 30; i++) { printf("%d ", Pos[i]); } printf("\n");*/ return 0; }
--- c4.s1079.cteam096.bugs.cpp.0.bugs.cpp +++ c4.s1308.cteam096.bugs.cpp.0.bugs.cpp @@ -95,5 +95,5 @@ getchar(); - for(int i = 0; i < t; i++) + for(int j = 0; j < t; j++) { nPos = 0; @@ -107,12 +107,19 @@ FindHops(n, m); - int i = 0; - for(Next(i, n); i <= n; Next(i, n)) + int k = 0; + for(Next(k, n); k <= n; Next(k, n)) { - putchar(Line[i]); + putchar(Line[k]); } } } + /*for(int i = 0; i < 30; i++) + { + printf("%d ", Pos[i]); + } + + printf("\n");*/ + return 0; }