Source code for submission s832

Go to diff to previous submission

bugs.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. using namespace std;
  20. #define DEBUG(x) cerr << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. //////////////////////////////////
  29.  
  30. #define MAXN 2222
  31. int shift[MAXN];
  32. int len;
  33. char input[MAXN];
  34. void kmp_init(){
  35. len = strlen(input);
  36. shift[0] = -1;
  37. for(int i = 0 , j = -1; i < len - 1; shift[++i] = ++j) while(j >= 0 && input[i] != input[j]) j = shift[j];
  38. }
  39. int krok(int I, char C){
  40. if((I < len-1) && (input[I+1] == C)) return I + 1;
  41. else if(I >= 0) return krok(shift[I], C);
  42. return -1;
  43. }
  44.  
  45. int N;
  46. char buf[2222222];
  47. int fail[2222222];
  48. void solve(){
  49. int pos = 0;
  50. fail[0] = -1;
  51. for(int i = 0; buf[i] != '\0'; i++){
  52. buf[pos] = buf[i];
  53. fail[pos + 1] = krok(fail[pos], buf[pos]);
  54. /*
  55.   if(input[fail[pos+1] + 1] == buf[i]) fail[pos+1]++;
  56.   else{
  57.   while(fail[pos + 1] >= 0 && buf[i] != input[fail[pos+1] + 1]){
  58.   //printf("failing: %d -> %d\n", fail[pos+1], shift[fail[pos+1]]);
  59.   fail[pos+1] = shift[fail[pos+1]];
  60.   }
  61.   if(fail[pos+1] >= 0) fail[pos+1]++;
  62.   }*/
  63. pos++;
  64. if(fail[pos] == len - 1) pos -= len;
  65. }
  66. buf[pos] = '\0';
  67. //REP(i, pos) printf("%d ", fail[i]);
  68. printf("%s\n", buf);
  69. }
  70.  
  71. int main() {
  72. while(scanf("%d %s", &N, input) != EOF){
  73. kmp_init();
  74. gets(buf);
  75. REP(i, N){
  76. gets(buf);
  77. solve();
  78. }
  79. }
  80. return 0;
  81. }
  82.  

Diff to submission s684

bugs.cpp

--- 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);
 }