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 2222 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; } int N; char buf[2222222]; int fail[2222222]; 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.s684.cteam002.bugs.cpp.0.bugs.cpp +++ c4.s832.cteam002.bugs.cpp.0.bugs.cpp @@ -37,4 +37,9 @@ 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; +} int N; @@ -46,13 +51,19 @@ for(int i = 0; buf[i] != '\0'; i++){ buf[pos] = buf[i]; - fail[pos + 1] = fail[pos]; + 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]]) fail[pos+1] = shift[fail[pos+1]]; - } + 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); }