Source code for submission s1308

Go to diff to previous submission

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) % MOD]] = i + 1;
  67. 			if(nPos < (m * 2) + 3)
  68. 			{
  69. 				nPos = 0;
  70. 				i = 0;
  71. 				q = 0;
  72. 			}
  73. 			else
  74. 			{
  75. 				nPos -= (m * 2) + 1;
  76. 				i = Pos[(nPos - 1) % 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 j = 0; j < t; j++)
  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 k = 0;
  110. 			for(Next(k, n); k <= n; Next(k, n))
  111. 			{
  112. 				putchar(Line[k]);
  113. 			}
  114. 		}
  115. 	}
  116.  
  117. 	/*for(int i = 0; i < 30; i++)
  118. 	{
  119. 		printf("%d ", Pos[i]);
  120. 	}
  121.  
  122. 	printf("\n");*/
  123.  
  124. 	return 0;
  125. }
  126.  

Diff to submission s1079

bugs.cpp

--- c4.s1079.cteam096.bugs.cpp.0.bugs.cpp
+++ c4.s1308.cteam096.bugs.cpp.0.bugs.cpp
@@ -95,5 +95,5 @@
                 
                 getchar();
-                for(int i = 0; i < t; i++)
+                for(int j = 0; j < t; j++)
                 {
                         nPos = 0;
@@ -107,12 +107,19 @@
                         
                         FindHops(n, m);
-                        int i = 0;
-                        for(Next(i, n); i <= n; Next(i, n))
+                        int k = 0;
+                        for(Next(k, n); k <= n; Next(k, n))
                         {
-                                putchar(Line[i]);
+                                putchar(Line[k]);
                         }
                 }
         }
         
+        /*for(int i = 0; i < 30; i++)
+        {
+                printf("%d ", Pos[i]);
+        }
+        
+        printf("\n");*/
+        
         return 0;
 }