Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.29 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.io.IOException;
  4.  
  5.  
  6. public class SDA1819T4 {
  7. /**
  8. * main adalah fungsi utama untuk input dan memanggil instruksi yang
  9. * sesuai dengan input instruksinya
  10. *
  11. * @param args Unused.
  12. * @return Nothing.
  13. */
  14. public static void main(String args[]) throws IOException {
  15. BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  16. String kata = reader.readLine();
  17. int jml = Integer.parseInt(reader.readLine());
  18. for (int i = 0; i < jml; i++) {
  19. String inp[] = reader.readLine().split(" ");
  20. if (inp[0].equals("0")) {
  21. System.out.println(query0(kata, inp[1]));
  22. } else if (inp[0].equals("1")) {
  23.  
  24. }
  25. }
  26. }
  27.  
  28. public static int query0(String inp, String str) {
  29. int pjgInp = inp.length();
  30. int pjgStr = str.length();
  31. if (pjgStr > pjgInp) {
  32. return 0;
  33. }
  34. String sub = inp.substring(0, pjgStr);
  35. int subHash1 = HashTable.hash1(sub);
  36. int subHash2 = HashTable.hash2(sub);
  37. int strHash1 = HashTable.hash1(str);
  38. int strHash2 = HashTable.hash2(str);
  39. int val = 0;
  40. for (int i = 0; i <= pjgInp - pjgStr; i++) {
  41. if (subHash1 == strHash1 && subHash2 == strHash2) {
  42. val++;
  43. }
  44. if (i + pjgStr > pjgInp - 1) {
  45. break;
  46. }
  47. char firstChar = inp.charAt(i);
  48. char lastChar = inp.charAt(i + pjgStr);
  49. int firstVal1 = (int) firstChar * (int) Math.pow(HashTable.BASE1, pjgStr - 1);
  50. int firstVal2 = (int) firstChar * (int) Math.pow(HashTable.BASE2, pjgStr - 1);
  51. int lastVal = (int) lastChar;
  52. subHash1 = (subHash1 - firstVal1) * HashTable.BASE1 + lastVal;
  53. subHash2 = (subHash2 - firstVal2) * HashTable.BASE2 + lastVal;
  54. }
  55. return val;
  56. }
  57.  
  58. // public static int query1(String inp) {
  59. // int pjgInp = inp.length();
  60. // int pjgStr, subHash1, subHash2;
  61. // String str;
  62. // String val = 0;
  63. // String subMax;
  64. // for (int i = 1; i < pjgInp; i++) {
  65. // str = inp.substring(0, i);
  66. // subHash1 = HashTable.hash1(str);
  67. // subHash2 = HashTable.hash2(str);
  68. // for (int j = 0; j <= pjgInp - i; j++) {
  69. // if (HashTable.exist(subHash1, subHash2)) {
  70. // HashTable.arr[subHash1] =
  71. // } else {
  72.  
  73. // }
  74. // }
  75. // }
  76. // }
  77. }
  78.  
  79. class Substring {
  80. public int hash2;
  81. public Substring coll = null;
  82. public int freq = 0;
  83.  
  84. public Substring(int hash2) {
  85. this.hash2 = hash2;
  86. }
  87. }
  88.  
  89. class HashTable {
  90. public static final int BASE1 = 31;
  91. public static final int BASE2 = 29;
  92. public static Substring[] arr = new Substring[98317];
  93.  
  94. public static int hash1(String str) {
  95. int pjg = str.length();
  96. int val = 0;
  97. int sub;
  98. for (int i = 0; i < pjg; i++) {
  99. sub = (int) str.charAt(i);
  100. val += sub * (Math.pow(BASE1, pjg - i - 1));
  101. }
  102. return val;
  103. }
  104.  
  105. public static int hash2(String str) {
  106. int pjg = str.length();
  107. int val = 0;
  108. int sub;
  109. for (int i = 0; i < pjg; i++) {
  110. sub = (int) str.charAt(i);
  111. val += sub * (Math.pow(BASE2, pjg - i - 1));
  112. }
  113. return val;
  114. }
  115.  
  116. public static boolean exist(int hash1, int hash2) {
  117. if (arr[hash1] == null) {
  118. return false;
  119. } else if (arr[hash1].hash2 == hash2) {
  120. return true;
  121. } else if (arr[hash1].coll == null) {
  122. return false;
  123. } else {
  124. Substring sub = arr[hash1].coll;
  125. if (sub.hash2 == hash2) {
  126. return true;
  127. }
  128. while (sub.coll != null) {
  129. sub = sub.coll;
  130. if (sub.hash2 == hash2) {
  131. return true;
  132. }
  133. }
  134. return false;
  135. }
  136. }
  137.  
  138. // public static void save(int hash1, int hash2) {
  139.  
  140. // }
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement