Advertisement
Guest User

Untitled

a guest
May 20th, 2019
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.80 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. public class Main {
  7. public static void main(String[] args) throws IOException {
  8. BufferedReader buff = new BufferedReader(new InputStreamReader(System.in));
  9. String[] parts = buff.readLine().split(" ");
  10. int n = Integer.parseInt(parts[0]);
  11. int t = Integer.parseInt(parts[1]);
  12. int k = Integer.parseInt(parts[2]);
  13.  
  14. int bolni = 0;
  15. int zdravi = 0;
  16.  
  17. for (int i = 0; i<n; i++){
  18. int total = 0;
  19. String naod = buff.readLine();
  20. for(int j = 0; j<k; j++){
  21. String[] parts2 = buff.readLine().split(" ");
  22. int zbir = search(naod.toCharArray(), parts2[0].toCharArray());
  23. if (zbir > Integer.parseInt(parts2[1]))
  24. total++;
  25. }
  26. if (total > t)
  27. bolni++;
  28. else
  29. zdravi++;
  30.  
  31. }
  32.  
  33. System.out.printf("%d %d", bolni, zdravi);
  34.  
  35. }
  36.  
  37.  
  38. static int NO_OF_CHARS = 256;
  39.  
  40. //A utility function to get maximum of two integers
  41. static int max (int a, int b) { return (a > b)? a: b; }
  42.  
  43. //The preprocessing function for Boyer Moore's
  44. //bad character heuristic
  45. static void badCharHeuristic( char []str, int size,int badchar[])
  46. {
  47. int i;
  48.  
  49. // Initialize all occurrences as -1
  50. for (i = 0; i < NO_OF_CHARS; i++)
  51. badchar[i] = -1;
  52.  
  53. // Fill the actual value of last occurrence
  54. // of a character
  55. for (i = 0; i < size; i++)
  56. badchar[(int) str[i]] = i;
  57. }
  58.  
  59. /* A pattern searching function that uses Bad
  60. Character Heuristic of Boyer Moore Algorithm */
  61. static int search( char txt[], char pat[])
  62. {
  63. int total = 0;
  64. int m = pat.length;
  65. int n = txt.length;
  66.  
  67. int badchar[] = new int[NO_OF_CHARS];
  68.  
  69. /* Fill the bad character array by calling
  70. the preprocessing function badCharHeuristic()
  71. for given pattern */
  72. badCharHeuristic(pat, m, badchar);
  73.  
  74. int s = 0; // s is shift of the pattern with
  75. // respect to text
  76. while(s <= (n - m))
  77. {
  78. int j = m-1;
  79.  
  80. /* Keep reducing index j of pattern while
  81. characters of pattern and text are
  82. matching at this shift s */
  83. while(j >= 0 && pat[j] == txt[s+j])
  84. j--;
  85.  
  86. /* If the pattern is present at current
  87. shift, then index j will become -1 after
  88. the above loop */
  89. if (j < 0)
  90. {
  91. //System.out.println("Patterns occur at shift = " + s);
  92. total++;
  93.  
  94. /* Shift the pattern so that the next
  95. character in text aligns with the last
  96. occurrence of it in pattern.
  97. The condition s+m < n is necessary for
  98. the case when pattern occurs at the end
  99. of text */
  100. s += (s+m < n)? m-badchar[txt[s+m]] : 1;
  101.  
  102. }
  103.  
  104. else
  105. /* Shift the pattern so that the bad character
  106. in text aligns with the last occurrence of
  107. it in pattern. The max function is used to
  108. make sure that we get a positive shift.
  109. We may get a negative shift if the last
  110. occurrence of bad character in pattern
  111. is on the right side of the current
  112. character. */
  113. s += max(1, j - badchar[txt[s+j]]);
  114. }
  115. return total;
  116. }
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement