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.