Source code for submission s740

bugs.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdint.h>
  5. #include <ctype.h>
  6. #include <math.h>
  7.  
  8. static char input[2000007];
  9. static char text[2000007];
  10. static int stav[2000007];
  11.  
  12. static char vzor[1007];
  13. static int automat[1007];
  14.  
  15. int main() {
  16.  
  17. int n;
  18. while ( scanf("%d %s", &n, vzor) != EOF ) {
  19.  
  20.  
  21. int vzor_len = strlen(vzor);
  22. // printf("vzor je '%s'\n", vzor);
  23.  
  24. int ii, i;
  25. for ( ii = 0; ii < n; ++ii ) {
  26.  
  27. // while ( getchar() != '\n' );
  28. fgets(input, sizeof(input), stdin);
  29.  
  30. automat[0] = 0;
  31. automat[1] = 0;
  32. int z = 0;
  33. int pos = -1;
  34. int text_len = strlen(input);
  35.  
  36. for ( i = 0; i < text_len; ++i )
  37. stav[i] = -1;
  38.  
  39. for ( i = 1; i < vzor_len-1; ++i ) {
  40. while ( z != 0 && vzor[z] != vzor[i] )
  41. z = automat[z];
  42. if ( vzor[z] == vzor[i] ) ++z;
  43. automat[i+1] = z;
  44. }
  45.  
  46. z = 0;
  47.  
  48. for ( i = 0; i < text_len; ++i ) {
  49.  
  50. if ( pos != -1 && stav[pos] != -1 )
  51. z = stav[pos];
  52.  
  53. // printf("write %d %c\n", pos+1, input[i]);
  54. text[++pos] = input[i];
  55. text[pos+1] = 0;
  56.  
  57. while ( z != 0 && vzor[z] != text[pos] )
  58. z = automat[z];
  59.  
  60. if ( vzor[z] == text[pos] )
  61. ++z;
  62.  
  63. stav[pos] = z;
  64. stav[pos+1] = -1;
  65.  
  66. if ( z == vzor_len ) {
  67. // printf("delete %d == %d\n", z, vzor_len);
  68. // printf("NULL on %d\n", pos-z+1);
  69. text[pos-z+1] = 0;
  70. pos = pos-z;
  71. // printf("new pos %d\n", pos);
  72. }
  73.  
  74. }
  75.  
  76. printf("%s", text);
  77.  
  78. }
  79.  
  80. }
  81.  
  82. return 0;
  83.  
  84. }
  85.