Source code for submission s583

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[back[b]+1]!=s[i]) {
  41. 			//printf("%d\n", b);
  42. 			b = back[b];
  43. 		}
  44. 		back[i] = b+1;
  45. 	}
  46. }
  47.  
  48. void kmp(char *t) {
  49. 	int X = strlen(t);
  50. 	int akt = 0;
  51. 	vector<int> poz;
  52. 	vector<char> znak;
  53. 	FOR (i, 0, X) {
  54. 		znak.push_back(t[i]);
  55. 		while (akt>-1 && t[i]!=s[akt+1])
  56. 			akt = back[akt];
  57. 		akt++;
  58. 		poz.push_back(akt);
  59. 		//printf("%d\n", akt);
  60. 		if (akt==N) {
  61. 			FOR (i, 0, N) {
  62. 				znak.pop_back();
  63. 				poz.pop_back();
  64. 			}
  65. 			akt = poz.back();
  66. 		}
  67. 	}
  68. 	FOR (i, 0, znak.size()) printf("%c", znak[i]);
  69. }
  70.  
  71. bool solve() {
  72. 		s[0] = '!'; if (scanf("%d %s", &T, s+1)<0) return false;
  73. 		getchar(); N = strlen(s+1);
  74. 		build();
  75. 		FOR (i, 0, T) {
  76. 			fgets(text, MAXT, stdin);
  77. 			kmp(text);
  78. 		}
  79. 		return true;
  80. }
  81.  
  82. int main() {
  83. 		while(solve());
  84. 		return 0;
  85. }