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 i = 0; i < t; i++) { 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 i = 0; for(Next(i, n); i <= n; Next(i, n)) { putchar(Line[i]); } } } return 0; }
--- c4.s986.cteam096.bugs.cpp.0.bugs.cpp +++ c4.s1079.cteam096.bugs.cpp.0.bugs.cpp @@ -64,6 +64,6 @@ if(q == m) { - Hop[Pos[(nPos - (m - 0)) % MOD]] = i + 1; - if(nPos < m * 2) + Hop[Pos[(nPos - m) % MOD]] = i + 1; + if(nPos < (m * 2) + 3) { nPos = 0; @@ -73,6 +73,6 @@ else { - nPos -= m * 2; - i = Pos[nPos % MOD]; + nPos -= (m * 2) + 1; + i = Pos[(nPos - 1) % MOD]; q = 0; }