Source code for submission s633

Go to diff to previous submission

bugs.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cctype>
  5. #include <climits>
  6. #include <cstring>
  7. #include <string>
  8. #include <algorithm>
  9. #include <deque>
  10. #include <list>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <vector>
  16.  
  17. #define FOR(I,A,B)	for(int I = (A); I < (B); ++I)
  18.  
  19. #define EPS 1e-9
  20. #define PI 3.14159265358979
  21.  
  22. using namespace std;
  23.  
  24. typedef pair<int, int> ii;
  25. typedef long long ll;
  26. typedef unsigned long long ull;
  27.  
  28. #define MAXT 2100000
  29. #define MAXN 1100
  30.  
  31. int N, T;
  32. char text[MAXT];
  33. char s[MAXN];
  34. int back[MAXN];
  35.  
  36. void build() {
  37. 	back[0] = -1; back[1] = 0;
  38. 	FOR (i, 2, N+1) {
  39. 		int b = back[i-1];
  40. 		while (b>-1 && s[b+1]!=s[i]) {
  41. 			//printf("b%d %c\n", b, s[i]);
  42. 			b = back[b];
  43. 		}
  44. 		back[i] = b+1;
  45. 		//printf("%d\n", back[i]);
  46. 	}
  47. }
  48.  
  49. void kmp(char *t) {
  50. 	int X = strlen(t);
  51. 	int akt = 0;
  52. 	vector<int> poz;
  53. 	vector<char> znak;
  54. 	FOR (i, 0, X) {
  55. 		znak.push_back(t[i]);
  56. 		while (akt>-1 && t[i]!=s[akt+1])
  57. 			akt = back[akt];
  58. 		akt++;
  59. 		poz.push_back(akt);
  60. 		//printf("%d\n", akt);
  61. 		if (akt==N) {
  62. 			FOR (i, 0, N) {
  63. 				znak.pop_back();
  64. 				poz.pop_back();
  65. 			}
  66. 			akt = poz.back();
  67. 		}
  68. 	}
  69. 	FOR (i, 0, znak.size()) printf("%c", znak[i]);
  70. }
  71.  
  72. bool solve() {
  73. 		s[0] = '!'; if (scanf("%d %s", &T, s+1)<0) return false;
  74. 		getchar(); N = strlen(s+1);
  75. 		build();
  76. 		FOR (i, 0, T) {
  77. 			fgets(text, MAXT, stdin);
  78. 			kmp(text);
  79. 		}
  80. 		return true;
  81. }
  82.  
  83. int main() {
  84. 		while(solve());
  85. 		return 0;
  86. }

Diff to submission s583

bugs.cpp

--- c4.s583.cteam014.bugs.cpp.0.bugs.cpp
+++ c4.s633.cteam014.bugs.cpp.0.bugs.cpp
@@ -38,9 +38,10 @@
         FOR (i, 2, N+1) {
                 int b = back[i-1];
-                while (b>-1 && s[back[b]+1]!=s[i]) {
-                        //printf("%d\n", b);
+                while (b>-1 && s[b+1]!=s[i]) {
+                        //printf("b%d %c\n", b, s[i]);
                         b = back[b];
                 }
                 back[i] = b+1;
+                //printf("%d\n", back[i]);
         }
 }