Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; ////////////////////////////////// #define MAXN 2222222 int shift[MAXN]; int len; char input[MAXN]; /*void kmp_init(){ len = strlen(input); shift[0] = -1; for(int i = 0 , j = -1; i < len - 1; shift[++i] = ++j) while(j >= 0 && input[i] != input[j]) j = shift[j]; }*/ int krok(int I, char C){ if((I < len-1) && (input[I+1] == C)) return I + 1; else if(I >= 0) return krok(shift[I], C); return -1; } void kmp_init(){ len = strlen(input); shift[0] = -1; for(int i = 1; i < len; i++) shift[i] = krok(shift[i-1], input[i]); } int N; char buf[MAXN]; int fail[MAXN]; void solve(){ int pos = 0; fail[0] = -1; for(int i = 0; buf[i] != '\0'; i++){ buf[pos] = buf[i]; fail[pos + 1] = krok(fail[pos], buf[pos]); /* if(input[fail[pos+1] + 1] == buf[i]) fail[pos+1]++; else{ while(fail[pos + 1] >= 0 && buf[i] != input[fail[pos+1] + 1]){ //printf("failing: %d -> %d\n", fail[pos+1], shift[fail[pos+1]]); fail[pos+1] = shift[fail[pos+1]]; } if(fail[pos+1] >= 0) fail[pos+1]++; }*/ pos++; if(fail[pos] == len - 1) pos -= len; } buf[pos] = '\0'; //REP(i, pos) printf("%d ", fail[i]); printf("%s\n", buf); } int main() { while(scanf("%d %s", &N, input) != EOF){ kmp_init(); gets(buf); REP(i, N){ gets(buf); solve(); } } return 0; }
--- c4.s832.cteam002.bugs.cpp.0.bugs.cpp +++ c4.s844.cteam002.bugs.cpp.0.bugs.cpp @@ -28,13 +28,13 @@ ////////////////////////////////// -#define MAXN 2222 +#define MAXN 2222222 int shift[MAXN]; int len; char input[MAXN]; -void kmp_init(){ +/*void kmp_init(){ len = strlen(input); shift[0] = -1; for(int i = 0 , j = -1; i < len - 1; shift[++i] = ++j) while(j >= 0 && input[i] != input[j]) j = shift[j]; -} +}*/ int krok(int I, char C){ if((I < len-1) && (input[I+1] == C)) return I + 1; @@ -42,8 +42,13 @@ return -1; } +void kmp_init(){ + len = strlen(input); + shift[0] = -1; + for(int i = 1; i < len; i++) shift[i] = krok(shift[i-1], input[i]); +} int N; -char buf[2222222]; -int fail[2222222]; +char buf[MAXN]; +int fail[MAXN]; void solve(){ int pos = 0;