Source code for submission s986

bugs.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAXN 3000000
  6. #define MAXM 4000
  7. #define MOD 10000
  8.  
  9. char Line[MAXN];
  10. int Hop[MAXN];
  11. char Bug[MAXM];
  12. int Pi[MAXM];
  13. int Pos[MOD];
  14. int nPos;
  15.  
  16. void Compute(int m)
  17. {
  18. Pi[1] = 0;
  19. int k = 0;
  20.  
  21. for(int q = 2; q <= m; q++)
  22. {
  23. while((k > 0) && (Bug[k + 1] != Bug[q]))
  24. {
  25. k = Pi[k];
  26. }
  27.  
  28. if(Bug[k + 1] == Bug[q])
  29. {
  30. k++;
  31. }
  32.  
  33. Pi[q] = k;
  34. }
  35. }
  36.  
  37. void Next(int& i, int n)
  38. {
  39. i++;
  40. while((i <= n) && (Hop[i]))
  41. {
  42. i = Hop[i];
  43. }
  44.  
  45. Pos[nPos++ % MOD] = i;
  46. }
  47.  
  48. void FindHops(int n, int m)
  49. {
  50. int q = 0;
  51. int i = 0;
  52. for(Next(i, n); i <= n; Next(i, n))
  53. {
  54. while((q > 0) && (Bug[q + 1] != Line[i]))
  55. {
  56. q = Pi[q];
  57. }
  58.  
  59. if(Bug[q + 1] == Line[i])
  60. {
  61. q++;
  62. }
  63.  
  64. if(q == m)
  65. {
  66. Hop[Pos[(nPos - (m - 0)) % MOD]] = i + 1;
  67. if(nPos < m * 2)
  68. {
  69. nPos = 0;
  70. i = 0;
  71. q = 0;
  72. }
  73. else
  74. {
  75. nPos -= m * 2;
  76. i = Pos[nPos % MOD];
  77. q = 0;
  78. }
  79. }
  80. }
  81. }
  82.  
  83. int main()
  84. {
  85. int t;
  86. while(scanf("%d%s", &t, Bug + 1) > 0)
  87. {
  88. int m = strlen(Bug + 1);
  89. for(int i = 0; i <= m; i++)
  90. {
  91. Pi[i] = 0;
  92. }
  93.  
  94. Compute(m);
  95.  
  96. getchar();
  97. for(int i = 0; i < t; i++)
  98. {
  99. nPos = 0;
  100. fgets(Line + 1, MAXN, stdin);
  101.  
  102. int n = strlen(Line + 1);
  103. for(int i = 0; i <= n; i++)
  104. {
  105. Hop[i] = 0;
  106. }
  107.  
  108. FindHops(n, m);
  109. int i = 0;
  110. for(Next(i, n); i <= n; Next(i, n))
  111. {
  112. putchar(Line[i]);
  113. }
  114. }
  115. }
  116.  
  117. return 0;
  118. }
  119.